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 G1, G2,... of finite graphs is given, then there always exist two indices i < j such that Gi is a minor of Gj. 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 Kh-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.

Read more about this topic:  Graph Minor

Famous quotes containing the words major, results and/or conjectures:

    When I see that the nineteenth century has crowned the idolatry of Art with the deification of Love, so that every poet is supposed to have pierced to the holy of holies when he has announced that Love is the Supreme, or the Enough, or the All, I feel that Art was safer in the hands of the most fanatical of Cromwell’s major generals than it will be if ever it gets into mine.
    George Bernard Shaw (1856–1950)

    There is not a single rule, however plausible, and however firmly grounded in epistemology, that is not violated at some time or other. It becomes evident that such violations are not accidental events, they are not results of insufficient knowledge or of inattention which might have been avoided. On the contrary, we see that they are necessary for progress.
    Paul Feyerabend (1924–1994)

    After all, it is putting a very high price on one’s conjectures to have a man roasted alive because of them.
    Michel de Montaigne (1533–1592)