Hadwiger Conjecture (graph Theory) - Generalizations

Generalizations

György Hajós conjectured that Hadwiger's conjecture could be strengthened to subdivisions rather than minors: that is, that every graph with chromatic number k contains a subdivision of a complete graph K_k. Hajós' conjecture is true for k ≤ 4, but Catlin (1979) found counterexamples to this strengthened conjecture for k ≥ 7; the cases k = 5 and k = 6 remain open. Erdős & Fajtlowicz (1981) observed that Hajós' conjecture fails badly for random graphs: for any ε > 0, in the limit as the number of vertices, n, goes to infinity, the probability approaches one that a random n-vertex graph has chromatic number ≥ (1/2 − ε)n / log₂ n, and that its largest clique subdivision has at most cn1/2 vertices for some constant c. In this context it is worth noting that the probability also approaches one that a random n-vertex graph has Hadwiger number greater than or equal to its chromatic number, so the Hadwiger conjecture holds for random graphs with high probability; more precisely, the Hadwiger number is with high probability a constant times n/√log n.

Borowiecki (1993) asked whether Hadwiger's conjecture could be extended to list coloring. For k ≤ 4, every graph with list chromatic number k has a k-vertex clique minor. However, the maximum list chromatic number of planar graphs is 5, not 4, so the extension fails already for K₅-minor-free graphs. More generally, for every t ≥ 1, there exist graphs whose Hadwiger number is 3t + 1 and whose list chromatic number is 4t + 1.

Gerards and Seymour conjectured that every graph G with chromatic number k has a complete graph K_k as an odd minor. Such a structure can be represented as a family of k vertex-disjoint subtrees of G, each of which is two-colored, such that each pair of subtrees is connected by a monochromatic edge. Although graphs with no odd K_k minor are not necessarily sparse, a similar upper bound holds for them as it does for the standard Hadwiger conjecture: a graph with no odd K_k minor has chromatic number χ(G) = O(k √log k).

By imposing more conditions on G than the number of colors it needs, it may be possible to prove the existence of larger minors than K_k. One example of this is the snark theorem, that every cubic graph requiring four colors in any edge coloring has the Petersen graph as a minor, conjectured by W. T. Tutte and announced to be proved in 2001 by Robertson, Sanders, Seymour, and Thomas.