Equivalent Forms
An equivalent form of the Hadwiger conjecture (the contrapositive of the form stated above) is that, if there is no sequence of edge contractions (each merging the two endpoints of some edge into a single supervertex) that brings graph G to the complete graph Kk, then G must have a vertex coloring with k − 1 colors.
Note that, in a minimal k-coloring of any graph G, contracting each color class of the coloring to a single vertex will produce a complete graph Kk. However, this contraction process does not produce a minor of G 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 graph Kk, in such a way that all the contracted sets are connected.
If Fk denotes the family of graphs having the property that all minors of graphs in Fk can be (k − 1)-colored, then it follows from the Robertson–Seymour theorem that Fk can be characterized by a finite set of forbidden minors. Hadwiger's conjecture is that this set consists of a single forbidden minor, Kk.
Read more about this topic: Hadwiger Conjecture (graph Theory)
Famous quotes containing the words equivalent and/or forms:
“Inter-railers are the ambulatory equivalent of McDonalds, walking testimony to the erosion of French culture.”
—Alice Thompson (b. 1963)
“This is a catastrophic universe, always; and subject to sudden reversals, upheavals, changes, cataclysms, with joy never anything but the song of substance under pressure forced into new forms and shapes.”
—Doris Lessing (b. 1919)