Hadwiger conjecture (graph theory)

One form of the Hadwiger conjecture is that, if there is no sequence of edge contractions (each merging the two endpoints of some edge into a single supervertex) that brings a graph G to the complete then G must have a vertex coloring with k-1 colors. Equivalently (the contrapositive of the same statement), if a given graph has no such coloring, then there is a way of contracting edges to produce K_k as a graph minor. In a minimal of any contracting each color class of the coloring to a single vertex will produce a complete However, this contraction process does not produce a minor because there is (by definition) no edge between any two vertices in the same color class, thus the contraction is not an edge contraction (which is required for minors). Hadwiger's conjecture states that there exists a different way of properly edge contracting sets of vertices to single vertices, producing a complete in such a way that all the contracted sets are connected. If \mathcal{F}_k denotes the family of graphs having the property that all minors of graphs in \mathcal{F}_k can be then it follows from the Robertson–Seymour theorem that \mathcal{F}_k can be characterized by a finite set of forbidden minors. Hadwiger's conjecture is that this set consists of a single forbidden The Hadwiger number h(G) of a graph G is the size k of the largest complete graph K_k that is a minor of G (or equivalently can be obtained by contracting edges It is also known as the contraction clique number The Hadwiger conjecture can be stated in the simple algebraic form \chi(G)\le h(G) where \chi(G) denotes the chromatic number ==Special cases and partial results==

The case k=2 is trivial: a graph requires more than one color if and only if it has an edge, and that edge is itself a K_2 minor. The case k=3 is also easy: the graphs requiring three colors are the non-bipartite graphs, and every non-bipartite graph has an odd cycle, which can be contracted to a 3-cycle, that is, a K_3 minor. In the same paper in which he introduced the conjecture, Hadwiger proved its truth The graphs with no K_4 minor are the series–parallel graphs and their subgraphs. Each graph of this type has a vertex with at most two incident edges; one can 3-color any such graph by removing one such vertex, coloring the remaining graph recursively, and then adding back and coloring the removed vertex. Because the removed vertex has at most two edges, one of the three colors will always be available to color it when the vertex is added back. The truth of the conjecture for k=5 implies the four color theorem: for, if the conjecture is true, every graph requiring five or more colors would have a K_5 minor and would (by Wagner's theorem) be nonplanar. Klaus Wagner proved in 1937 that the case k=5 is actually equivalent to the four color theorem and therefore we now know it to be true. As Wagner showed, every graph that has no K_5 minor can be decomposed via clique-sums into pieces that are either planar or an 8-vertex Möbius ladder, and each of these pieces can be 4-colored independently of each other, so the 4-colorability of a K_5-minor-free graph follows from the 4-colorability of each of the planar pieces. proved the conjecture also using the four color theorem; their paper with this proof won the 1994 Fulkerson Prize. It follows from their proof that linklessly embeddable graphs, a three-dimensional analogue of planar graphs, have chromatic number at most five. Due to this result, the conjecture is known to be true but it remains unsolved for For k=7, some partial results are known: every 7-chromatic graph must contain either a K_7 minor or both a K_{4,4} minor and a K_{3,5} minor. Every graph G has a vertex with at most O\bigl(h(G)\sqrt{\log h(G)}\bigr) incident edges, from which it follows that a greedy coloring algorithm that removes this low-degree vertex, colors the remaining graph, and then adds back the removed vertex and colors it, will color the given graph with O\bigl(h(G)\sqrt{\log h(G)}\bigr) colors. In the 1980s, Alexander V. Kostochka and Andrew Thomason both independently proved that every graph with no K_k minor has average degree O (k \sqrt {\log k}) and can thus be colored using O (k \sqrt {\log k}) colors. A sequence of improvements to this bound have led to a proof of O(k \log \log k)-colorability for graphs without K_k ==Generalizations==

György Hajós conjectured (not to be confused with the Hajós conjecture on graph decomposition into cycles) 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 Hajós' conjecture is true but found counterexamples to this strengthened conjecture the cases k=5 and k=6 remain observed that Hajós' conjecture fails badly for random graphs: for in the limit as the number of vertices, goes to infinity, the probability approaches one that a random graph has chromatic and that its largest clique subdivision has O(\sqrt n) vertices. In this context, it is worth noting that the probability also approaches one that a random 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 proportional {{nowrap|to n/\sqrt{\log n}.}} asked whether Hadwiger's conjecture could be extended to list coloring. every graph with list chromatic number k has a clique minor. However, the maximum list chromatic number of planar graphs is 5, not 4, so the extension fails already for graphs. More generally, for there exist graphs whose Hadwiger number is 3t+1 and whose list chromatic number 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 {{nowrap|\chi(G)=O\bigl(k\sqrt{\log k}\bigr).}} A 2025 preprint claims a lower bound of (\tfrac32-o(1))k, disproving this conjecture. By imposing extra conditions on G, it may be possible to prove the existence of larger minors One example 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. ==Notes==