O'Reilly logo

Topics in Topological Graph Theory by Jonathan L. Gross, Robin J. Wilson, Lowell W. Beineke

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

5Graph minors: generalizing Kuratowski’s theorem

R. BRUCE RICHTER

1. Introduction

2. Graph decompositions

3. Linked decompositions

4. Graphs with bounded tree-width

5. Finding large grids

6. Embedding large grids

References

        In their Graph Minors Project, Robertson and Seymour proved that, in any infinite set of graphs, one is a minor of another. In particular, if S is a surface, the set of minor-minimal graphs that are not embeddable in S is finite.

            Two central results of the Graph Minors Project are:

  • if the graphs in the infinite set have bounded tree-width, then one is a minor of the other;
  • graphs with large tree-width have large grids as minors.

        We present the ‘simple’ proofs of these two facts, and adapt an argument ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required