Simplicial Decompositions, Tree-decompositions and Graph Minors

Reinhard Diestel, Cambridge

This paper gives a summary of open problems and recent results concerning the existence and uniqueness of simplicial decompositions (Halin) and tree-decompositions (Robertson/Seymour) into primes.

All graphs considered in this paper are finite or countably infinite. Let G be a graph, σ > 0 an ordinal, and let B_{λ} be an induced subgraph of G for every λ < σ. The family F = (B_{λ})_{λ<σ} is called a simplicial tree-decomposition of G if the following four conditions hold. (S1) G = ⋃_{λ<σ} B_{λ} (S2) (⋃_{λ<μ} B_{λ}) ∩ B_{μ} =: S_{μ} is a complete graph for each μ (0 < μ < σ) (S3) No S_{μ} contains B_{μ} or any other B_{λ} (0 ≤ λ < μ < σ) (S4) Each S_{μ} is contained in B_{λ} for some λ < μ (μ < σ) If F satisfies (S1)–(S3) but not necessarily (S4), F is called a simplicial decomposition of G. If F satisfies (S1), (S3) and (S4), F is called a tree-decomposition of G. We shall usually call complete graphs simplices (as is the custom in the field) and refer to the S_{μ}’s in (S2) as simplices of attachment.

The concepts of simplicial decompositions, tree-decompositions and simplicial tree-decompositions were all inspired by a common forerunner: the decompositions of finite graphs used by K. Wagner in his classic paper [ 13 ], in which he proved the equivalence of the 4-Colour-Conjecture to Hadwiger’s Conjecture for n = 5.

To show that the 4CC implies Hadwiger’s Conjecture (for n = 5), Wagner used the following idea. He considered all (edge-maximal finite) graphs not subcontracting to K_{5}, and proved that breaking up any such graph along separating complete subgraphs (‘simplices’) leaves factors that are either planar or isomorphic to a certain 3-chromatic non-planar graph. Assuming the 4CC, these factors are therefore 4-colourable, a property which can be lifted back to the original graph.

Wagner’s decompositions were later redefined—and named ‘simplicial decompositions’—by Halin [ 9 ], to make them suitable for infinite graphs; the definition given by Halin is equivalent to our conditions (S1)–(S3). It is an interesting fact that for finite graphs the conditions (S1)–(S3) imply (S4), which is not the case for infinite graphs. Thus, with the transition to infinite graphs based on (S1)–(S3), one of the most striking features of Wagner’s finite decompositions was lost: their ‘tree shape’, a consequence of (S4) (see [ 2 ] for details).

It was this ‘tree shape’ that gave rise to the other generalization of Wagner’s decompositions: the ‘tree-decompositions’ recently introduced by Robertson and Seymour [ 12 ]. Robertson and Seymour’s definition of a tree-decomposition (again for finite graphs) is equivalent to our conditions (S1), (S3) and (S4).

Thus simplicial tree-decompositions, as defined above, are simplicial decompositions as well as tree-decompositions. They are therefore a generalization of Wagner’s decompositions to infinite graphs in the structural sense mentioned, while at the same time maintaining their compatibility with graph properties such as the chromatic number.

The compatibility of simplicial tree-decompositions with various natural graph properties has been the basis for a number of applications. Most notably, Wagner and Halin used simplicial tree-decompositions to characterize a number of graph properties given in terms of forbidden minors; see [ 13–15 ] and [ 8,10 ], or [ 11, p.188 ] for an overview. A more recent application of simplicial tree-decompositions can be found in [ 1 ].

On the other hand, simplicial tree-decompositions provide a fascinating object of study in themselves. They have turned out to possess a number of very natural features [ 2 ], and some of their most basic properties are still unknown.

The following two questions are perhaps the most basic ones one would ask about any kind of graph decomposition. Firstly, does every graph admit a decomposition into primes, that is, into graphs that cannot be decomposed further? And secondly, if a graph has a decomposition into primes, to what extent will this decomposition be uniquely determined?

This paper summarizes recent progress on these questions for tree-decomposi-tions and simplicial tree-decompositions, and lists some of the problems that remain open. In order to get by with a minimum of terminology, we shall adopt an informal style, give precedence to examples over theorems (except for the main results), and treat most technicalities with generous disregard. For a more rigorous exposition the reader is referred to [ 2–5 ].

Let us first consider the existence of prime decompositions. We shall call a graph prime with respect to a given type of decomposition if it has no such decomposition into more than one factor. For example, a graph is prime with respect to simplicial decompositions and with respect to simplicial tree-decompositions if and only if it contains no separating simplex. (It is not difficult to see that any graph with a nontrivial simplicial decompositions needs separating simplices to serve as simplices of attachment [ 2 ].) Similarly, a graph is prime with respect to tree-decompositions if and only if it has no separating subgraph whatsoever, i.e., iff it is itself a simplex.

As an example, consider the graph G shown in Fig. 1. G admits the simplicial tree-decomposition (T_{1}, T_{2}, T_{3}, T_{4}). The factors T_{i} in this decomposition are triangles, and therefore prime. Thus (T_{1}, T_{2}, T_{3}, T_{4}) is a simplicial tree-decomposition of G into primes.

The following problem was raised by Halin [ 9 ] in (1964), and it is in its generality still unsolved:

Problem. Determine the graphs that admit a simplicial decomposition into primes.

For finite graphs this problem does not arise: it is not difficult to show that every finite graph admits a simplicial decomposition into primes (see Halin [ 11 ]).

FIGURE 1. Prime factors of a graph

Moreover, Halin [ 9 ] was able to extend this result to graphs of any cardinality which do not contain an infinite simplex. For countable graphs and simplicial tree-decom-positions (the most ‘genuine’ infinite simplicial decompositions, because of their tree shape), characterizations of the graphs admitting a prime decomposition were given in [ 3 ] and [ 5 ]; see below. The most extensive study of the general problem can be found in [ 7 ], one of the last papers of G. A. Dirac.

When Halin posed the above problem in [ 9 ], he also showed that graphs not admitting a simplicial decomposition into primes exist. The following graph is a variation of Halin’s example: let S = S [ s_{1}, s_{2}, …] be an infinite simplex, P = x_{1}x_{2} … a one-way infinite path, and let H_{1} be the graph obtained from the disjoint union of S and P by drawing the edges x_{i}s_{j} for all i ≥ j and joining one additional vertex q to all vertices in S (Fig. 2).

FIGURE 2. H_{1}—the prototype counterexample?

H_{1} admits a simplicial decomposition into primes: for example, the decomposition

F = (X_{1}, X_{2}, X_{3}, …, Y) ,

where

X_{i} : = H_{1} [ x_{i}, x_{i+1}, s_{1}, …, s_{i}]

and

Y : = H_{1} [ s_{1}, s_{2}, s_{3} …, q] .

However, F is not a tree-decomposition: the simplex of attachment of the last factor Y is S, which is not contained in any of the earlier factors X_{i} (cf. (S4)). Notice that this problem is not just due to an unfortunate choice of the factors X_{i}: since x_{i} is separated from s_{i+1} by the simplex H_{1} [ x_{i+1}, s_{1}, …, s_{i}] for each i, no vertex of P can be in a common prime induced subgraph of H_{1} with all vertices of S. (We express this fact by saying that S has no prime extension into P.)

The following theorem, proved in [ 3 ], implies that H_{1} does in fact not admit a simplicial tree-decomposition into primes, and that the obstruction we encountered in trying to find one lies at the heart of the matter.

If G is a graph, S ⊂ G, and C is a component of G\S, let S [ C] denote the subgraph of S induced by all vertices that have a neighbour in C. If S [ C] = S, we shall call S attached to C.

Theorem 1. A countable graph G has a simplicial tree-decomposition into primes if and only if G satisfies the following condition: (†) If S ⊂ G is a simplex, C and C′ are distinct components of G\S, and S is

attached to C, then S [ C′] has a prime extension into C. (Fig. 3)

FIGURE 3. An extension X of S [ C′] into C

It is a rather striking phenomenon that long after Halin had published his original example of a graph not admitting a prime decomposition, no essentially different such ‘counterexample’ had been found; see e.g. Dirac [ 7 ]. Indeed, all graphs G without a simplicial tree-decomposition into primes seem to have a structure very much like that of H_{1}: they all seem to contain an infinite simplex S separating G into components C and C′, where S is attached to C, G [ C ∪ S] is covered by a family (X_{1}, X_{2}, …) of convex subgraphs (although not necessarily simplices) that have the same intersection pattern with S and with each other as in the case of H_{1}, and S [ C′] is not contained in any one of the X_{i}. (A subgraph X of G is convex in G if any induced path in G connecting vertices of X is contained in X.) It is then only a small step further to notice that contracting C′ to a single vertex q and shrinking the subgraphs X_{i} a little gives one a contraction of G [ C ∪ S] onto H_{1}.

And indeed,

(∗) Any graph not admitting a simplicial tree-decomposition into primes has a minor isomorphic to H_{1}.

How about the converse of (∗)—that is, how far is (∗) from being a characterization of the graphs that admit simplicial tree-decompositions into primes?

Notice that the graph property of not containing H_{1} as a minor is closed under taking minors. Thus we can only hope to characterize the prime-decomposable graphs by this property if they share this feature, i.e., if minors of decomposable graphs are again decomposable. Or more intuitively, if we seek to express our observation that H_{1} is in a sense the ‘simplest’ non-decomposable graph by using the minor relation, then this relation and our notion of ‘simpler’ should match: a minor of a graph with a prime decomposition should itself admit a prime decomposition, and this should be at most as complex as that of the original graph.

With the usual concept of a minor, however, this is far from true. Recall that a minor of a graph G is obtained in two steps:

(1) taking a subgraph of G, and

(2) contracting edges of the subgraph. Clearly, both these steps are too general to meet our above requirement; that is, if G is a graph that has a relatively simple prime decomposition, and if H is obtained from G by either of the two steps, then H may only admit much more complex prime decompositions, or even none at all.

For example, if G is an infinite simplex and thus admits the trivial prime decomposition consisting only of itself, we can find subgraphs in G with arbitrarily complex or even no prime decompositions, including H_{1}. An only slightly more complicated example shows that even if we restrict step (1) to taking induced subgraphs it still allows us to obtain H_{1} from a prime graph: if we add a new vertex to H_{1} and join it to all old vertices by independent paths of length at least 2, the resulting graph is prime (because it has no separating simplex) and contains H_{1} as an induced subgraph.

As an example for step (2), consider the graph G obtained by identifying two cycles of order 10 along 3 consecutive vertices x, y, z. Then G is prime, but contracting the edges xy and yz results in a graph that has a separating simplex (the contracted vertex), and therefore only a non-trivial prime decomposition into two factors. Or more extremely, if we subdivide every edge of H_{1} once, the resulting graph will again be prime (and therefore admit the trivial prime decomposition), but we can reobtain H_{1} from it only by contracting the appropriate edges.

Thus if we want the converse of (∗) to hold, we have to restrict the definition of a minor by sharpening both of the above steps.

Let us call two vertices of a graph simplicially close if they are not separated by any simplex, and let us call H a simplicial minor of G if H is obtained from G by

(1′) taking a convex subgraph of G, and

(2′) contracting edges of this convex subgraph in such a way that simplicially close vertices remain simplicially close.

It is easily seen that this restricted concept of a minor no longer admits the examples we considered above. And indeed, simplicial minors satisfy the converse of (∗):

(∗∗) If H_{1} is a simplicial minor of G, then G admits no simplicial tree-decomposition into primes.

In order to achieve (∗∗), we had to come down a long way from the most general concept of a minor that formed the basis of (∗). It would therefore not be surprising if we now had to pay for the gain of (∗∗) with the loss of (∗), that is, if not admitting a prime decomposition no longer implied the existence of certain (simplicial) minors like H_{1}.

The following main theorem of [ 5 ] asserts that this is not the case: the graphs admitting a simplicial tree-decomposition into primes are characterized by only two forbidden simplicial minors, H_{1} and its counterpart H_{2}, obtained from H_{1} by filling in all missing edges of the form x_{i}x_{j}.

Theorem 2. A countable graph G admits a simplicial tree-decomposition into primes if and only if neither H_{1} nor H_{2} is a simplicial minor of G.

Theorem 2 has a corresponding version for tree-decompositions, also proved in [ 5 ]:

Theorem 3. A countable graph has a tree-decomposition into primes if and only if it is chordal and neither H_{1} nor H_{2} is its simplicial minor.

Let us now briefly address the second question regarding prime decompositions, the question of uniqueness.

Problem. Which graphs have a (simplicial) (tree-) decomposition into a unique set of primes?

The finite case of this problem is again easy: every finite graph has a simplicial tree-decomposition into a unique set of primes, see Halin [ 11 ]. The primes of a finite graph can be obtained by iteratively splitting it along separating simplices.

In general however, a prime decomposition need not be unique. Consider, for example, the graph H′_{1} := H_{1}\{ q }. H′_{1} admits the simplicial tree-decompositions

F = (S, X_{1}, X_{2}, X_{3}, …)

and

F′ = (X_{1}, X_{2}, X_{3}, …) .

Thus, while F is a perfectly acceptable simplicial tree-decomposition, its factor S is in a sense redundant: if we omit it, the remaining factors still form a prime decomposition of H′_{1}.

Let us call a simplicial tree-decomposition reduced if it has no such redundant factors. Reduced prime decompositions are by far the most ‘common’ kind; for example, all prime decompositions into finite factors are reduced [ 4 ].

The following result was obtained in [ 4 ]:

Theorem 4. If a countable graph has a reduced simplicial tree-decomposition into primes, then its factors and simplices of attachment in any such decomposition are uniquely determined.

The immediate question arising from this result is whether every graph that has some simplicial tree-decomposition into primes also has a reduced such decomposition— in which case prime decompositions could in practice be taken reduced as a matter of course. However, this is not the case; [ 4 ] contains an example of a graph that has a simplicial tree-decomposition into primes but no reduced prime decomposition: the ‘transitive closure’ T_{0} of the infinite dyadic tree.

Again, T_{0} seems to be ‘essentially’ the only example of such a graph:

Problem. Is T_{0} in some sense contained in every countable graph that admits a simplicial tree-decomposition into primes but no reduced such decomposition?

Let us finally mention a problem that is almost as fundamental as the quest for prime decompositions, and certainly of no less interest: the problem of which graphs admit a prime decomposition into finite factors.

It is easily seen that any simplicial decomposition into finite factors satisfies (S4), and is therefore even a simplicial tree-decomposition. Moreover, if a graph has a simplicial (tree-) decomposition into finite factors, then these factors can be split further into primes, extending the decomposition to a prime decomposition of the graph. A satisfactory characterization of the graphs that admit a decomposition into finite factors would therefore also characterize the graphs admitting a decomposition into finite primes.

Problem. Which graphs admit a simplicial decomposition into finite factors?

References

[ 1 ] R. Diestel, A separation property of planar triangulations, J. Graph Theory 11 (1987), 43–52. [ 2 ] R. Diestel, Simplicial tree-decompositions of infinite graphs I, submitted. [ 3 ] R. Diestel, Simplicial tree-decompositions of infinite graphs II—the existence of prime decom-

positions, submitted. [ 4 ] R. Diestel, Simplicial tree-decompositions of infinite graphs III—the uniqueness of prime de-

compositions, submitted. [ 5 ] R. Diestel, Simplicial minors and decompositions of graphs, Math. Proc. Camb. Phil. Soc. , to

appear. [ 6 ] R. Diestel, Tree-decompositions, tree-representability and chordal graphs, submitted. [ 7 ] G. A. Dirac, Simplicial decompositions of infinite graphs, Symp. Math. Roma XVIII (1986),

159–195. [ 8 ] R. Halin, Über einen Satz von K. Wagner zum Vierfarbenproblem, Math. Ann. 153 (1964),

47–62. [ 9 ] R. Halin, Simpliziale Zerfällungen beliebiger (endlicher oder unendlicher) Graphen, Math. Ann.

156 (1964), 216–225. [ 10 ] R. Halin, Zur Klassifikation der endlichen Graphen nach H. Hadwiger und K. Wagner, Math.

Ann. 172 (1967), 46–78. [ 11 ] R. Halin, Graphentheorie II, Wissenschaftliche Buchgesellschaft, Darmstadt 1981. Math. Ann.

152 (1963), 75–94. [ 12 ] N. Robertson and P. D. Seymour, Graph minors I–XVIII, J. Combin. Theory B , to appear. [ 13 ] K. Wagner, Über eine Eigenschaft der ebenen Komplexe, Math. Ann. 114 (1937), 570–590. [ 14 ] K. Wagner, Über eine Erweiterung eines Satzes von Kuratowski, Deutsche Math. 2 (1937),

280–285. [ 15 ] K. Wagner, Bemerkungen zu Hadwigers Vermutung, Math. Ann. 141 (1960), 433–451.