##

### 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)