O'Reilly logo

Topics in Structural Graph Theory by Ortrud R. Oellermann, 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

7

Tree-width and graph minors

DIETER RAUTENBACH and BRUCE REED

1   Introduction

2   Subtree intersection representation

3   Tree decomposition and tree-width

4   Tree decompositions decompose

5   Excluding planar minors

6   Wagner’s conjecture

7   The dual of tree-width

8   A canonical tree decomposition

9   Wagner’s conjecture for arbitrary graphs

10   Efficient characterization of H-minor-free graphs

References

In this chapter, we discuss tree decompositions, motivating our treatment by discussing how they are used in the characterization of H -minor-free graphs. We focus in particular on one invariant of tree decompositions, their width, which is of central importance. We also outline the proof of Wagner’s conjecture as one of the main results ...

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