average degree and can thus be colored using colors. A sequence of improvements to this bound have led to the announcement of -colorability for graphs without 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 contains a subdivision of a complete Hajós' conjecture is true but found counterexamples to this strengthened conjecture the cases and 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 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 asked whether Hadwiger's conjecture could be extended to list coloring. every graph with list chromatic number 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 and whose list chromatic number Gerards and Seymour conjectured that every graph with chromatic number has a complete graph as an odd minor. Such a structure can be represented as a family of vertex-disjoint subtrees of , each of which is two-colored, such that each pair of subtrees is connected by a monochromatic edge. Although graphs with no odd 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 minor has chromatic number By imposing extra conditions on , 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 References Graph coloring Graph minor theory Conjectures Unsolved problems in graph theory