Reinhard Diestel

Graph Decompositions: a study in infinite graph theory

Oxford University Press 1990
Hardback, 242 pages
ISBN 0-19-853210-5
UK Price: £37.50

This book is a research monograph offering a comprehensive treatment of the theory of simplicial decompositions of graphs. In modern terms, these are tree-decompositions in which the overlap between adjacent parts is always a complete subgraph (or simplex). For a finite graph, such decompositions can be obtained by recursively decomposing the graph along complete separators; for infinite graphs, this process does not necessarily terminate and may hence fail to decompose the graph into irreducible parts. Every simplicial decomposition of a graph casts it into a tree-structure - where for infinite graphs this may be a (well-founded) order tree, ie. have limit points - and indeed the modern tree-decompositions introduced by Halin in the 1970s and made more widely known by Robertson and Seymour in their proof of the Graph Minor Theorem (`Wagner's Conjecture') were modelled on simplicial decompositions.

Simplicial decompositions were introduced by Klaus Wagner in his 1935 thesis, where he used them to prove what is now called his equivalence theorem: the fact that the 4-colour-theorem is equivalent to Hadwiger's conjecture for 5. (To prove that a graph without a K5 minor can be 4-coloured, Wagner decomposed edge-maximal such graphs along complete separators, and showed that the irreducible parts obtained are either planar or isomorphic to one special 3-chromatic graph W.)

Wagner himself, and later Halin, Jørgensen, Mader, Robertson, Thomassen and others, went on to use simplicial decompositions for what has grown into a fair number of characterization theorems describing the (tree) structure of the graphs without a certain given minor. The book includes a chapter on applications of simplicial decompositions such as these.

The main part of the book, however, is devoted to the theory of simplicial decompositions of infinite graphs, and in particular to the problem of which graphs admit such a decomposition into irreducible parts. There are interesting structural characterization theorems of those graphs, but several challenging problems remain open: for example, no structural characterization is known of the graphs that admit a simplicial decomposition into finite parts.

Zentralblatt review of the book

OUP's page on the book (including an order form)