Graph Minor - Major Results and Conjectures

Major Results and Conjectures

It is straightforward to verify that the graph minor relation forms a partial order on the isomorphism classes of undirected graphs: it satisfies the transitive property (a minor of a minor of G is a minor of G itself), and G and H can only be minors of each other if they are isomorphic because any nontrivial minor operation removes edges. A deep result by Neil Robertson and Paul Seymour states that this partial order is actually a well-quasi-ordering: if an infinite list G₁, G₂,... of finite graphs is given, then there always exist two indices i < j such that G_i is a minor of G_j. Another equivalent way of stating this is that any set of graphs can have only a finite number of minimal elements under the minor ordering. This result proved a conjecture formerly known as Wagner's conjecture, after Klaus Wagner; Wagner had conjectured it long earlier, but only published it in 1970.

In the course of their proof, Seymour and Robertson also prove the graph structure theorem in which they determine, for any fixed graph H, the rough structure of any graph which does not have H as a minor. The statement of the theorem is itself long and involved, but in short it establishes that such a graph must have the structure of a clique-sum of smaller graphs that are modified in small ways from graphs embedded on surfaces of bounded genus. Thus, their theory establishes fundamental connections between graph minors and topological embeddings of graphs.

For any graph H, the simple H-minor-free graphs must be sparse, which means that the number of edges is less than some constant multiple of the number of vertices. More specifically, if H has h vertices, then a simple n-vertex simple H-minor-free graph can have at most edges, and some K_h-minor-free graphs have at least this many edges. Additionally, the H-minor-free graphs have a separator theorem similar to the planar separator theorem for planar graphs: for any fixed H, and any n-vertex H-minor-free graph G, it is possible to find a subset of O(√n) vertices the removal of which splits G into two (possibly disconnected) subgraphs with at most 2n/3 vertices per subgraph.

The Hadwiger conjecture in graph theory proposes that if a graph G does not contain a minor isomorphic to the complete graph on k vertices, then G has a proper coloring with k − 1 colors. The case k = 5 is a restatement of the four color theorem. The Hadwiger conjecture has been proven only for k ≤ 6, but remains unproven in the general case. Bollobás, Catlin & Erdős (1980) call it “one of the deepest unsolved problems in graph theory.” Another result relating the four-color theorem to graph minors is the snark theorem announced by Robertson, Sanders, Seymour, and Thomas, a strengthening of the four-color theorem conjectured by W. T. Tutte and stating that any bridgeless 3-regular graph that requires four colors in an edge coloring must have the Petersen graph as a minor.