Recent Excluded Minor Theorems for Graphs
Robin B. Thomas · Cambridge University Press eBooks · 1999
A graph is a minor of another if the first can be obtained from a subgraph of the second by contracting edges. An excluded minor theorem describes the structure of graphs with no minor isomorphic to a prescribed set of graphs. Splitter theorems are tools for proving excluded minor theorems. We discuss splitter theorems for internally 4-connected graphs and for cyclically 5-connected cubic graphs, the graph minor theorem of Robertson and Seymour, linkless embeddings of graphs in 3-space, Hadwiger's conjecture on t -colourability of graphs with no K t +1 minor, Tutte's edge 3-colouring conjecture on edge 3-colourability of 2-connected cubic graphs with no Petersen minor, and Pfaffian orientations of bipartite graphs. The latter are related to the even directed circuit problem, a problem of Pólya about permanents, the 2-colourability of hypergraphs, and sign-nonsingular matrices. Introduction All graphs in this paper are finite, and may have loops and parallel edges. A graph is a minor of another if the first can be obtained from a subgraph of the second by contracting edges. An H minor is a minor isomorphic to H . The following is Wagner's reformulation [75] of Kuratowski's theorem [27]. Theorem 1.1 A graph is planar if and only if it has no minor isomorphic to K 5 or K 3,3 . Kuratowski's theorem is important, because it gives a good characterization (in the sense of J. Edmonds) of planarity, but we can also think of it as a structural theorem characterizing graphs with no K 5 or K 3,3 minor.