Book contents
- Frontmatter
- Contents
- Preface
- The Rado Lecture
- The Invited Lectures
- Polynomials in Finite Geometries
- Applications of Combinatorial Designs to Communications, Cryptography, and Networking
- Random Walks on Combinatorial Objects
- Bose–Burton Type Theorems for Finite Projective, Affine and Polar Spaces
- Geometric Graph Theory
- Recent Excluded Minor Theorems for Graphs
- Parity, Cycle Space, and K4-Subdivisions in Graphs
Recent Excluded Minor Theorems for Graphs
Published online by Cambridge University Press: 05 May 2013
- Frontmatter
- Contents
- Preface
- The Rado Lecture
- The Invited Lectures
- Polynomials in Finite Geometries
- Applications of Combinatorial Designs to Communications, Cryptography, and Networking
- Random Walks on Combinatorial Objects
- Bose–Burton Type Theorems for Finite Projective, Affine and Polar Spaces
- Geometric Graph Theory
- Recent Excluded Minor Theorems for Graphs
- Parity, Cycle Space, and K4-Subdivisions in Graphs
Summary
Summary 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 Kt+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.1A graph is planar if and only if it has no minor isomorphic to K5 or K3,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 K5 or K3,3 minor.
- Type
- Chapter
- Information
- Surveys in Combinatorics, 1999 , pp. 201 - 222Publisher: Cambridge University PressPrint publication year: 1999
- 12
- Cited by