The analogue of Hadwiger’s conjecture for the immersion order states that every graph G contains K X(G) as an immersion. Our work is motivated by a strengthening of this conjecture which asserts that every graph G contains K X(G) as a totally odd immersion. As evidence for this strengthened conjecture and inspired by a result of Steiner (2024), we show that if the chromatic number of G is equal to any of its topological lower bounds, then G contains a totally odd immersion of K [x( G)/2] +1 . Kneser graphs are canonical examples of graphs satisfying such equalities for their chromatic numbers. Simonyi and Zsban (2010) showed that every Kneser graph G with large enough order (compared to x (G) ) contains a totally odd subdivision of K X(G) , thus satisfying the motivating conjecture in a strong sense. We show that, in fact, for every t ≥ 8, there are t -chromatic Kneser graphs that contain arbitrarily large complete totally odd subdivisions.

The counterexamples that Catlin used to disprove Hajós’ conjecture (For every integer t ≥ 0, every graph G with no subdivision of K t+1 is t- colorable.) are the lexicographic product of cliques and cycles. In 1989, Lescure and Meyniel made a conjecture that is a weakening of Hajós’ and that remains open: For every integer t ≥ 0, every graph G with no immersion of K t+1 is t- colorable. Can minimal counterexamples to this conjecture be produced through graph products? Collins, Heenehan, and McDonald recently gave a negative answer to this question for the lexicographic and Cartesian product. We consider a strengthening of the Lescure and Meyniel conjecture, different from that of Hajós, based on the notion of totally odd immersions. We study the largest totally odd immersion appearing in the graph product of two graphs. Our results imply that no minimal counterexample to this strengthened conjecture can be obtained from the Cartesian, lexicographic, direct (tensor) or strong product of graphs.

The exact distance p-power of a graph G, denoted G[#p], is a graph on vertex set V(G) in which two vertices are adjacent if they are at distance exactly p in G. Given integers k and p, we define f(k, p) to be the maximum possible order of a clique in the exact distance p-powers of graphs with maximum degree k + 1. It is easily observed that f(k, 2) ≤ k2 + k + 1. We prove that equality may only hold if a connected component of G is isomorphic to a member of the class Pk of incidence graphs of finite projective k-geometries. (These famous combinatorial structures are known to exist when k is a prime power, and are conjectured not to exist for other values of k.) We then study the case of graphs of maximum degree k + 1 with clique number k2 + k. One way to obtain such a graph is to remove a vertex from a graph in P k; we call Pk' the class of all such resulting graphs. We prove that for any graph G of maximum degree k + 1 whose exact square has a (k2 + k)-clique, either G has a subgraph isomorphic to a graph in P’k, or a connected component of G is a (k + 1)-regular bipartite graph of order 2(k2 + k). We call Ok the class of such bipartite graphs, and study their structural properties. These properties imply that (if they exist) the graphs in Ok must be highly symmetric. Using this structural information, we show that O2 contains only one graph, known as the Franklin graph. We then show that O3 also consists of a single graph, which we build. Furthermore, we show that O4 and O5 are empty. For general values of p, we prove that f(k, p) ≤ (k + 1)k[p/2] + 1, and that the bound is tight for every odd integer p ≥ 3. This implies that f(k, 2) = f(k, 3) whenever there exists a finite projective k-geometry, however, in such a case, the bound of f(k, 3) could also be reached by highly symmetric graphs built from a finite k-geometry, which is not the case for other values of k.