Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Hadwiger conjecture (graph theory)
Summary
In graph theory, the Hadwiger conjecture states that if is loopless and has no minor then its chromatic number satisfies . It is known to be true for . The conjecture is a generalization of the four-color theorem and is considered to be one of the most important and challenging open problems in the field.
In more detail, if all proper colorings of an undirected graph use or more colors, then one can find disjoint connected subgraphs of such that each subgraph is connected by an edge to each other subgraph. Contracting the edges within each of these subgraphs so that each subgraph collapses to a single vertex produces a complete graph on vertices as a minor of .
This conjecture, a far-reaching generalization of the four-color problem, was made by Hugo Hadwiger in 1943 and is still unsolved. call it "one of the deepest unsolved problems in graph theory."
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 a graph to the complete graph , then must have a vertex coloring with colors.
In a minimal -coloring of any graph , contracting each color class of the coloring to a single vertex will produce a complete graph . However, this contraction process does not produce a minor of 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 , in such a way that all the contracted sets are connected.
If denotes the family of graphs having the property that all minors of graphs in can be -colored, then it follows from the Robertson–Seymour theorem that can be characterized by a finite set of forbidden minors. Hadwiger's conjecture is that this set consists of a single forbidden minor, .
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.