Encyclopedia > H > Hadwiger conjecture (graph theory)
Hadwiger conjecture (graph theory)
In graph theory, the Hadwiger conjecture (or "Hadwiger's conjecture") states that, if the complete graph on k vertices, K_k, is not a minor of a graph G, then G has a vertex coloring with k-1 colors. Equivalently, if there is no sequence of edge contractions (each identifying the two endpoints of an edge) that brings graph G to the complete graph K_k, then G has a vertex coloring with k-1 colors.
Information are taken from Wikipedia, the open encyclopedia, to which contribute many volunteers from around the whole world. Texts are available under the following conditions GNU Free Documentation License.
Encyklopedie (cz) Encyklopédia (sk) Enzyklopädie (de)