Tree-decompositions, Tree-representability and Chordal Graphs

Reinhard Diestel

Department of Pure Mathematics University of Cambridge 16 Mill Lane Cambridge, England

In this note we combine results of Halin [ 5 ] and the author [ 3 ] to a theorem concerning the relationship between two graph properties: the property of being chordal and that of being tree-representable. A graph is chordal if all its induced cycles are triangles, and it is tree-representable if it is isomorphic to the intersection graph of a family of subtrees of some tree. (If T is a tree and T = (T_{i})_{i^{∈}I} is a family of subtrees of T, the intersection graph of T is the graph with vertex set T and edge set { T_{i}T_{j} | T_{i} ∩ T_{j} ≠ ∅ }.)

Our theorem identifies the tree-representable graphs as the chordal graphs not containing two specified simplicial minors. These chordal graphs are in turn precisely the graphs admitting a tree-decomposition (in the sense of Robertson and Seymour [ 6 ]) into primes.

It is easily seen that every tree-representable graph must be chordal. The converse, however, is less clear: is every chordal graph tree-representable?

For finite graphs this is indeed so; this result was obtained independently by Buneman [ 1 ] and Gavril [ 4 ].

The infinite case of the tree-representability problem seems somewhat more involved. It was shown by Halin [ 5 ] that infinite chordal graphs are not necessarily tree-represent-able, and that the tree-representability of an infinite chordal graph is equivalent to the existence of a certain kind of decomposition of the graph. This will be made more precise later.

The following two graphs, H_{1} and H_{2}, are variations of Halin’s example of a graph that is chordal but not tree-representable.

Define H_{1} as follows. Let S be a countably infinite complete graph, with V (S) = { s_{1}, s_{2}, … } say. Add a one-way infinite path P = x_{1}x_{2} … and a single vertex q, join x_{i} to s_{j} iff i ≥ j, and let q be adjacent to all vertices in S but to none in P.

Let H_{2} be the graph obtained from H_{1} by adding all missing edges between vertices x_{i} and x_{j}, i ≠ j, thus turning P into a complete subgraph of H_{2} (Fig. 1).

It is easily checked that H_{1} and H_{2} are chordal, but it is already less straightforward to show that these graphs are not tree-representable. Yet as we shall see in Theorem 1, H_{1} and H_{2} are not only not tree-representable themselves, they are in a sense the prototypes of all countable graphs that are not tree-representable.

To make this more precise, we have to introduce some terminology.

Figure 1

Let us call two vertices v, w of a graph G simplicially close in G if G has no complete subgraph that separates v and w in G. For example, if G is a cycle then any two vertices of G are simplicially close, but vertices of a tree are only simplicially close if they are adjacent.

A subgraph H of a graph G is called convex in G if H contains every induced path in G whose endvertices are in H. For example, if G = H ∪ H′ and H ∩ H′ is complete, then H and H′ are convex subgraphs of G.

The concepts of simplicial closeness and convexity play a central role in the theory of simplicial decompositions; see for example [ 2 ].

If G, G′ are graphs and f : V (G) → V (G′) is surjective, f is called a homomorphism from G onto G′ if

vw ^{∈} E(G) ⇒ (f(v)f(w) ^{∈} E(G′) ∨ f(v) = f(w))

and

v′w′ ^{∈} E(G′) ⇒ ∃ vw ^{∈} E(G) : (f(v) = v′ ∧ f(w) = w′).

Moreover, f is called contractive if G [ f^{−1}(v) ] is connected for every v ^{∈} V (G′), and f is simplicial if f is contractive and preserves simplicial closeness. Thus if f is a simplicial homomorphism from G onto G′, then v′, w′ ^{∈} V (G′) can only be separated by a complete subgraph of G′ if, for every two vertices v ^{∈} f^{−1}(v′) and w ^{∈} f^{−1}(w′), there exists a complete subgraph in G that separates v from w.

H′ is said to be a minor of G if G has a subgraph H from which there exists a contractive homomorphism f onto H′. We shall call H′ a simplicial minor of G, if H and f can be chosen in such a way that H is convex in G and f is simplicial.

We can now state our characterization theorem for tree-representable graphs.

Theorem 1. A countable graph is tree-representable if and only if it is chordal and neither H_{1} nor H_{2} is its simplicial minor.

The proof of Theorem 1 is a spin-off from two more powerful results. The first of these is the main theorem of Halin [ 5 ], which links tree-representability to the existence problem of simplicial tree-decompositions into primes. The other result is the main theorem of [ 3 ], which states that such a decomposition exists precisely if neither of H_{1}, H_{2} is a simplicial minor of the graph in question. For a proof of Theorem 1 it will therefore suffice to give a precise definition of these decompositions and to state the main results of [ 5 ] and [ 3 ].

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 tree-decomposition of G if it satisfies (S1), (S3) and (S4) of the following four conditions. (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 also satisfies (S2), F is called a simplicial tree-decomposition of G. A graph is prime with respect to either of these two types of decomposition if it has no such decomposition into more than one factor B_{λ}, and a (simplicial) tree-decomposition whose every factor is prime is called a (simplicial) tree-decomposition into primes. (An introduction to simplicial tree-decompositions can be found in [ 2 ].)

Theorem 2. [ 5 ] A chordal graph is tree-representable if and only if it admits a simplicial tree-decomposition into primes.

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

Let us now turn to the connection between Theorem 1 and tree-decompositions. It is not difficult to show that a graph is prime with respect to tree-decompositions if and only if it is complete. If a graph G has a tree-decomposition (B_{λ})_{λ<σ} into primes, the factors B_{λ} in this decomposition must therefore be the cliques of G, so G must be chordal (induction on μ). Furthermore, the countable graphs that admit a tree-decomposition into primes are determined among the chordal graphs by precisely the same forbidden simplicial minors as the tree-representable graphs are: a countable graph admits a tree-decomposition into primes if and only if it is chordal and neither H_{1} nor H_{2} is its simplicial minor [ 3 ].

We can therefore extend Theorem 1 as follows.

Theorem 1′. For any countable graph G the following assertions are equivalent. (i) G is tree-representable; (ii) G admits a tree-decomposition into primes; (iii) G is chordal, and neither H_{1} nor H_{2} is its simplicial minor.

References

1. P. Buneman, A characterization of rigid circuit graphs, Discrete Math. 9 (1974), 205–212.

2. R. Diestel, Simplicial tree-decompositions of infinite graphs I, submitted.

3. R. Diestel, Simplicial minors and decompositions of graphs, submitted.

4. F. Gavril, The intersection graphs of subtrees in trees are exactly the chordal graphs, J. Combin. Theory B 16 (1974), 47–56.

5. R. Halin, On the representation of triangulated graphs in trees, Europ. J. Combinatorics 5 (1984), 23–28.

6. N. Robertson and R. Seymour, Graph minors, J. Combin. Theory B , appearing.