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:
“But then people don’t read literature in order to understand; they read it because they want to re-live the feelings and sensations which they found exciting in the past. Art can be a lot of things; but in actual practice, most of it is merely the mental equivalent of alcohol and cantharides.”
—Aldous Huxley (1894–1963)
“Literary works cannot be taken over like factories, or literary forms of expression like industrial methods. Realist writing, of which history offers many widely varying examples, is likewise conditioned by the question of how, when and for what class it is made use of.”
—Bertolt Brecht (1898–1956)