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:
“Perhaps basketball and poetry have just a few things in common, but the most important is the possibility of transcendence. The opposite is labor. In writing, every writer knows when he or she is laboring to achieve an effect. You want to get from here to there, but find yourself willing it, forcing it. The equivalent in basketball is aiming your shot, a kind of strained and usually ineffective purposefulness. What you want is to be in some kind of flow, each next moment a discovery.”
—Stephen Dunn (b. 1939)
“It is not however, adulthood itself, but parenthood that forms the glass shroud of memory. For there is an interesting quirk in the memory of women. At 30, women see their adolescence quite clearly. At 30 a woman’s adolescence remains a facet fitting into her current self.... At 40, however, memories of adolescence are blurred. Women of this age look much more to their earlier childhood for memories of themselves and of their mothers. This links up to her typical parenting phase.”
—Terri Apter (20th century)