���������� �������������� �� ������� � ������ �� ������������

Reinhard Diestel, Cambridge

We survey applications of simplicial decompositions (decompositions by separating complete subgraphs) to problems in graph theory. Among the areas of application are excluded minor theorems, extremal graph theorems, chordal and interval graphs, infinite graph theory and algorithmic aspects.

Let G be a graph, σ > 0 an ordinal (possibly finite), and let B_{λ} be an induced subgraph of G for every λ < σ. The family F = (B_{λ})_{λ<σ} is called a simplicial decomposition of G if the following conditions hold. (S1) G = ⋃_{λ<σ} B_{λ}; (S2) Each subgraph (⋃_{λ<μ} B_{λ}) ∩ B_{μ} =: S_{μ} is complete (0 < μ < σ);

(S_{μ} is called the simplex of attachment of B_{μ}) (S3) No S_{μ} contains B_{μ} or any other B_{λ} (0 ≤ λ < μ < σ). For finite graphs, these three conditions imply a fourth [ 13 ]: (S4) Each S_{μ} is contained in B_{λ} for some λ < μ (μ < σ).

Notice that (S4) forces the factors of F into a tree structure: picking a fixed ‘predecessor’ λ =: τ(μ) for each μ < σ as in (S4) (i.e., such that S_{μ} ⊂ B_{τ(μ)}), we obtain a tree T_{F} (G) with vertex set { B_{λ} | λ < σ } and edge set { B_{μ}B_{τ(μ)} | μ < σ }. A family F satisfying (S1) and (S4) (but not necessarily (S2) or (S3)) is therefore called a tree-decomposition of G, and a family satisfying all four conditions (S1)–(S4) is a simplicial tree-decomposition of G (Fig. 1).

FIGURE 1. A simplicial tree-decomposition

A simplicial decomposition none of whose members in turn admits a simplicial decomposition into more than one factor is called a decomposition into primes, or a prime decomposition. All finite graphs have prime decompositions, and so do all infinite graphs not containing an infinite complete subgraph [ 33 ].

The existing applications of simplicial decompositions to problems in graph theory can be roughly divided into two categories. The first kind of application typically exploits the inductive nature of their definition and the information provided by (S2): the fact that all attachment graphs S_{μ} are simplices (complete graphs) often allows one to lift assertions about the factors to similar assertions about the whole graph. For example, if each factor of G admits a k-colouring of its vertices, then so does G: since all vertices in S_{μ} must be coloured differently, a simple permutation of colours will adjust any k-colouring of B_{μ} to a given k-colouring of S_{μ}, and hence to any given k-colouring of G|_{μ} := ⋃_{λ<μ} B_{λ}; thus by induction, G can be k-coloured if every B_{λ} can.

The other line of application of simplicial decompositions places the emphasis on their tree-shape. Condition (S2) is used only to ensure (S4), and is otherwise eroded by considering not the decomposition of G itself but the decompositions induced on its subgraphs H (see e.g. [ 62 ]). As the attachment graphs S_{μ} ∩ H will not in general be complete, such a decomposition of H may no longer be a simplicial decomposition. It will, however, still be a tree-decomposition (at least in the finite case), because it inherits (S4) from the decomposition of G. However, it is usually more convenient in such cases to work with the more general tree-decompositions rather than with simplicial decompositions in the first place.

Most of the results surveyed in this paper belong to the first of these two types of application of simplicial decompositions. Not that those of the second kind were not exciting: the results on well-quasi-ordering and embeddings of graphs recently achieved by Robertson and Seymour [ 61 ] are largely applications of tree-decompositions and would thus belong in this category. However, the object of this survey is more modest: it aims to bring to wider attention a number of interesting older results which have remained largely unknown (see particularly Section 1), to show the variety of ways in which simplicial and related decompositions can or could be used, and to present some open problems from the various fields of application.

1. Excluded Minor Theorems

Let H and X be graphs. In analogy to the familiar notation of TX for subdivisions of X (or ‘topological’ X graphs) we say that H is an HX (H for ‘homomorphism’) if its vertex set V (H) admits a partition { V_{x} | x ^{∈} V (X) } into branch sets V_{x} spanning connected subgraphs in H, such that H contains a V_{x}–V_{y} edge if and only if x and y are adjacent in X. If H is an HX and H is a subgraph of G, then X is called a minor of G. For finite G this is equivalent to saying that X is obtained from a subgraph of G by contracting edges. The partition sets V_{x} may or may not be required to be finite; since we shall only consider finite minors (for which the sets V_{x} can be made finite without loss of generality), such a restriction will lead to equivalent results.

If X is a set of graphs, we write TX := { TX | X ^{∈} X } and HX := { HX | X ^{∈} X }. We shall use G(H) to denote { G | H ^{∈} H ⇒ H ⊄ G }; for example, G(HX) contains the graphs without a minor in X, and G(TC_{4}) consists of the graphs in which every cycle is a triangle.

The classical prototype of an excluded minor theorem is Kuratowski’s characterization of planar graphs: a finite graph G is planar if and only if neither K_{5} nor K_{3,3} is a minor of G. Thus in our notation, the finite planar graphs are precisely the finite elements of G(HK_{5}, HK_{3,3}) (or, as in Kuratowski’s original version of the theorem, the finite elements of G(TK_{5}, TK_{3,3})).

The importance of Kuratowski’s theorem has traditionally been attributed to the fact that while planarity is easy to verify (using a concrete drawing in the plane), the equivalent property of not containing a K_{5} or K_{3,3} minor is easy to falsify (using a concrete HK_{5} or HK_{3,3} subgraph). Thus, whether we want to sell a certain graph as planar or as non-planar, by Kuratowski’s theorem there is always an efficient way of convincing our customers.

This feature of Kuratowski’s theorem is common to all excluded minor theorems, and indeed is their raison d’être: they all assert the equivalence of some stuctural graph property (which is easy to verify but difficult to falsify) with the absence of certain minors (which is easy to falsify but difficult to verify). The emphasis in such equivalence theorems can lie on either side: sometimes the structural property is ‘natural’ and comes first (as with planarity), while in other cases the excluded minors are given and the task is to descibe the structure of the graphs not containing them. (Excluded minor theorems of a somewhat different kind have recently been considered by Truemper [ 65 ].)

Since the minor relation is transitive, any class of the form G(HX) is closed under taking minors. Conversely, it is easily seen that any graph property G which is closed under taking minors has this form: if \overline{G} denotes the complement of G, then clearly G = G(H\overline{G}). Moreover, if we restrict ourselves to finite graphs, the recent well-quasi-ordering theorem of Robertson and Seymour [ 61 ] (‘Wagner’s conjecture’) tells us that \overline{G} can in fact always be replaced with a finite set of excluded minors. In other words: a property of finite graphs is closed under taking minors if and only if it has the form G(HX_{1}, …, HX_{n}).

In this paper we are interested in properties of graphs whose structure can be described in terms of simplicial decompositions. If such a property is closed under taking minors, as is the case in the following example, it gives rise to an excluded minor theorem.

The example, motivated by applications in computer science, was suggested by Chvátal and is due to Arnborg, Corneil and Proskurowski [ 2 ]. Call a graph a k-tree if it is recursively obtained from a K_{k} by the operation of joining a new vertex to all vertices in some complete subgraph of order k. Thus, a k-tree (≠ K_{k}) is simply a graph that admits a simplicial decomposition into K_{k+1}’s, all simplices of attachment having order k. The graphs considered in [ 2 ] are the partial k-trees, the subgraphs of k-trees. These are precisely the graphs having tree-width at most k—the tree-width of G is the smallest k such that G admits a tree-decomposition into factors of order at most k + 1—, which is a minor-closed property. The partial k-trees are therefore characterized by a unique minimal set of forbidden minors. Arnborg, Corneil and Proskurowski determined these minors for k = 3 as K_{5}, the octahedron K_{2,2,2}, the Wagner graph W (the octagon with its four diagonals) and the 5-prism C_{5} × K_{2} (the cartesian product of a 5-cycle with an edge). We remark that although the graphs considered in [ 2 ] are finite, the result extends to infinite graphs.

In the above example we started out from a structural graph property and had to find the corresponding excluded minors. In a sense, simplicial decompositions were merely incidental to the problem: the property considered happened to involve them, but they were not needed to solve the problem. And naturally, the genuine applications of simplicial decompositions are found in the excluded minor theorems of the opposite type: a list of forbidden minors is given, and simplicial decompositions are used to describe the structure of the graphs not containing these minors.

The first such theorem was proved by Wagner in 1937—which is how simplicial decompositions were introduced. Wagner set out to explore how far we would be ‘taken out of the plane’ by graphs that were no longer forbidden to contain either K_{5} or K_{3,3} minors (as in Kuratowski’s theorem), but only one of these two types. In particular, the question was whether the chromatic number of graphs not containing a K_{5} minor (but possibly one isomorphic to K_{3,3}) might be higher than that of planar graphs. The fact that this is not so but rather that all such graphs can be 4-coloured (as can planar graphs) is now usually known as the case of k = 5 of the (later) conjecture of Hadwiger:

H(k) : χ(G) ≥ k ⇒ G ⊃ HK_{k}  (∀ k ^{∈} ℕ),

or equivalently,

G ^{∈} G(HK_{k}) ⇒ χ(G) ≤ k − 1 .

As indicated earlier, a graph admits a k-colouring if and only its simplicial factors do (in any given decomposition); for a proof of H(5) it is therefore sufficient to show that all possible factors in prime decompositions of graphs in G(HK_{5}) can be 4-coloured. Moreover, since the chromatic number of a graph cannot increase through the deleting of edges, Wagner could restrict his consideration to prime factors of graphs that are edge-maximal in G(HK_{5}), i.e., in which the addition of any new edge creates an HK_{5}. (It is easily seen that every graph in G(HK_{5}) can be made edge-maximal by adding edges, and we remark that every graph in G(HK_{5}) admits a simplicial decomposition into primes.) And indeed, it turned out that all possible primes of edge-maximal graphs in G(HK_{5}) can be 4-coloured: they are either planar or isomorphic to the 3-chromatic graph W, the octagon with its four diagonals. (At the time of Wagner’s paper, the 4-colourability of planar graphs was, of course, still the 4-Colour-Conjecture, and for this reason Wagner’s result has become known as his ‘equivalence theorem’, establishing as it does the equivalence of the 4CC with Hadwiger’s Conjecture for k = 5.)

TABLE 1. The structure of the edge-maximal graphs G in classes of the form G(HX) 5 TABLE 1 (continued). The structure of the edge-maximal graphs G in classes of the form G(HX)

6

Wagner’s characterization of G(HK_{5}) in terms of simplicial decompositions set the trend for a number of similar excluded minor theorems, which are listed in Table 1. The general pattern is that a set X of finite graphs is given (the excluded minors), and that the theorem determines the homomorphism base B(HX) of X, which is the set of graphs that can occur as factors in prime decompositions of edge-maximal graphs in G(HX). In addition, the theorem usually gives some structural information on the precise manner in which the base elements have to be composed in order to give the edge-maximal graphs in G(HX). This information typically takes the form of prescibing the order |S_{μ}| of the simplices of attachment, sometimes depending on the type of the factors in which they are contained. (For a very simple example of how such a theorem is typically proved, the reader is referred to the determination of B(TK_{2,3}) (= B(HK_{2,3})) in [ 10 ].)

Three remarks should be made at this point. Firstly, the restriction that all excluded minors be finite is essential: it ensures that every graph of G(HX) is indeed contained in some edge-maximal element of G(HX) (this is not so, for example, with G(HP_{∞})), and that all these graphs admit a unique simplicial decomposition into primes [ 33 ]. (For a more thorough discussion of the problem of uniqueness and existence of prime decompositions see [ 13, 14 ].)

Secondly, unless otherwise stated no restriction is imposed on the order of the graphs G ^{∈} G(HX). However, by a theorem of Halin [ 35 ] elements of homomorphism bases are always countable, regardless of the cardinality of the graphs in G(HX) of which they are prime factors.

The third remark concerns small elements of the homomorphism base B(HX). If the smallest graph in X has order n, then clearly all graphs of order < n are in G(HX), and every complete graph of order < n is in B(HX) (because it is trivially edge-maximal and admits only the trivial prime decomposition, itself being the only factor). Such small complete graphs are therefore not listed among the elements of homomorphism bases in Table 1, unless they appear (non-trivially) in prime decompositions of graphs of order at least min { |X| : X ^{∈} X }.

The excluded minor theorems shown in Table 1 lend themselves to the deduction of various corollaries, which can sometimes be rather surprising. For example, any graph of chromatic number or minimal degree ≥ 6 contains minors isomorphic to the graphs L and K_{1,2,3}, any graph of minimal degree ≥ 5 contains minors isomorphic to W_{1,5} and to the prism (consider the last factor in any prime decomposition of an edge-maximal graph in G(HW_{1,5}) or G(H(C_{3} × K_{2}))), any graph of minimal degree ≥ 4 has a K_{5}^{−} minor, and so on. Or to mention just one more example, which can be read out of the excluded minor theorem for K_{1,2,3}: if G is a 3-connected non-planar graph of order ≥ 11, then G not only has a minor isomorphic to either K_{3,3} or K_{5} (as by Kuratowski)—it must have a minor isomorphic to K_{1,2,3}, a K_{3,3} plus two adjacent edges.

It is worth pointing out that all the above investigations can be carried out in a completely analogous fashion for forbidden subdivisions rather than minors. If a graph property G has the form G = G(TX), where X is again any set of finite graphs, then every graph G ^{∈} G can be extended to an edge-maximal member of G, and all graphs in G admit simplicial decompositions into primes. The set of graphs that can occur as factors in prime decompositions of edge-maximal graphs in G(TX) is then called the subdivision base of X, and denoted by B(TX).

Given the great deal of information a homomorphism or subdivision base characterization offers, it seems desirable to know for which sets X there is any reasonable hope to determine the corresponding base. For example, it would be a big step forward to be able to decide in which cases such a base is countable: if it is, it may be worth the effort trying to determine its elements constructively, whereas otherwise there would be little hope of doing so. However, very little is known in this direction, even if X consists of only one excluded minor:

Problem 1.1. For which finite graphs X is B(TX) or B(HX) countable? In particular, for which X does B(TX) or B(HX) consist entirely of finite graphs?

Let us provisionally call a homomorphism base simple if it is countable, or (alternatively) if all its elements are finite. (It is not known whether these two conditions coincide, that is, whether there exists a countable homomorphism base containing an infinite graph.)

Judging from what little evidence is available regarding Problem 1.1, it seems that denser excluded minors are less likely to have a simple base than sparser ones. For example, it was shown in [ 11 ] that B(TX) and B(HX) are uncountable if X = K_{n} or X = K_{n,m} with n, m ≥ 5, or if X is such that any two vertices have at least two common neighbours. In another theorem of [ 11 ], B(TX) and B(HX) are shown to be uncountable for any

X = { X | α(X) ≥ n } ,

where n ≥ 5, and α denotes minimal degree, vertex-connectivity, edge-connectivity, degree of regularity or chromatic number −1. (Table 1 shows that the bases in the first three of these cases are countable for n ≤ 4.)

To get a handle on Problem 1.1, it would be useful to know something about the relationship between different sets of graphs with simple bases. The following conjecture (whose first part is taken from [ 11 ]) is aimed in this direction.

Conjecture 1.2.

(i) If B(HX) is simple and X′ is obtained from X by deleting an edge, then B(HX′) is simple.

(ii) If B(HX) is simple and X′ is obtained from X by contracting an edge, then B(HX′) is simple.

(iii) If B(HX) is simple and X′ ⊃ X, then B(HX′) is simple.

Note that part (iii) of Conjecture 1.2 implies parts (i) and (ii), because G(HX) = G(HY) for Y = { Y | Y ⊃ HX }.

Parts (i) and (ii) of Conjecture 1.2 together say that, for single graphs X, the property of having a simple homomorphism base is itself closed under taking minors. Assuming this as true, one might find the evidence of Table 1 tempting to make the following conjecture:

Conjecture 1.3. B(HX) is simple if and only if X is planar.

Conjecture 1.3, though perhaps born more of wishful thinking than insight, is made particularly attractive by the fact that the planarity or non-planarity of an excluded minor determines whether the corresponding class of graphs has bounded tree-width: by a result of Robertson and Seymour [ 61 ], the tree-widths of the graphs in G(HX) have a uniform finite bound if and only if X is planar. (In [ 61 ] this is proved for finite graphs only; the extension to infinite graphs—but still with finite X—is due to R. Thomas.) However, it is not clear how much the order of a homomorphism base B(HX) or of its elements has to do with the tree-width of the graphs in G(HX):

Problem 1.4. Is there a connection between the simplicity of a homomorphism base B(HX) and the tree-width of the graphs in G(HX)? In particular, is it true that B(HX) is simple if and only if the graphs in G(HX) have bounded tree-width?

It is clear that a positive answer to the second question in Problem 1.4 would imply Conjecture 1.2 (iii) (and hence the whole of Conjecture 1.2), as well as Conjecture 1.3 (by the remarks above).

Finally, it may be worth recording a more immediate problem about homomorphism bases, whose solution would nevertheless clarify the situation considerably. If a graph G is edge-maximal in G(HX) and prime, then clearly G^{∈} B(HX), because G has only the trivial prime decomposition with itself as the only factor. Conversely however, a homomorphism base may contain graphs which are not themselves edge-maximal, but only (as by the definition of a homomorphism base) prime factors of larger edge-maximal graphs. And although it is not difficult to construct examples of such bases, in most ‘natural’ cases the homomorphism base of a graph X does seem to coincide with the class of prime and edge-maximal elements of G(HX).

Problem 1.5. For which X are all elements of B(HX) edge-maximal graphs in G(HX)?

2. Extremal Graphs

When the edge-maximal graphs in a class of the form G(H) are known, we have a fairly good overview of all graphs in G(H), since they are precisely the subgraphs of the edgemaximal ones. However, in cases where it is too difficult to determine all the edge-maximal members of such a class, it may still be possible to characterize an important subset of them: the so-called extremal graphs in G(H). A graph G ^{∈} G(H) of order n is called extremal in G(H) if it has the largest possible size (number of edges) that any n-graph in G(H) can have; this size is denoted by ex (n; H) [ 3 ]. Since this definition makes sense only for finite graphs, we shall assume for this section that all graphs considered are finite.

As in general a given graph G^{∈} G(H) will not necessarily be a subgraph of an extremal member of G(H), a characterization of these extremal graphs cannot be expected to give us the same amount of information as, say, the theorems listed in Table 1. However, it will at least provide one important bit of information: it will tell us how many edges force an n-graph to contain an element of H. In addition, a typical extremal graph theorem also determines the structure of the extremal graphs, and this structure is often quite simple.

Table 2 lists a number of extremal graph theorems where the structure of the extremal graphs can be described in terms of simplicial decompositions. In most cases the graph property involved is again given by one or two excluded minors; in order to accomodate other forbidden structures in the same table, however, the forbidden configurations, including minors, are uniformly expressed as excluded subgraphs.

The extremal size ex (n; H) of an n-graph in G(H) is in all our cases roughly given by a linear polynomial in n. Its exact value however may vary a little for different values of n, depending on features like the parity of n. The polynomial shown under ex (n; H) in Table 2 always marks the top edge of this variation: for each n ^{∈} ℕ it is at least as large as ex (n; H), with equality for infinitely many values of n. Similarly, the structural information provided refers only to (all) those extremal graphs in G(H) for whose size the value given under ex (n; H) is attained. Thus, a convenient translation of a row in Table 2 (with entries HX / p(n) / B_{1}, B_{2} / k / … / … / say) into an extremal graph theorem would be, ‘If G has n vertices and at least p(n) edges, then G contains an HX as a subgraph (or: X as a minor), unless G has size exactly p(n) and admits a simplicial decomposition into factors B_{1} or B_{2}, in which every simplex of attachment has order k; conversely, any graph with such a decomposition has size p(n) and is extremal in G(HX)’.

TABLE 2. The simplicial structure of extremal graphs in G(H) 11

3. Chordal Graphs

A graph is called chordal (or sometimes ‘triangulated’) if it has no induced cycles other than triangles, that is, if every cycle of length ≥ 4 has a chord. Chordal and related graphs have been studied extensively in recent years, and it would be a formidable task well beyond the scope of this paper to survey even only those results that can be proved using simplicial decompositions. Instead, we shall largely confine ourselves to pointing out the theorems that link simplicial decompositions with these graphs, thus forming the basis for the various applications.

The first of these theorems is now a classic. It is due to Dirac, and in its original form it describes the structure of all finite chordal graphs. However, the theorem extends easily to all graphs that admit a simplicial decomposition into primes. Recall that a clique is a maximal complete subgraph.

Theorem 3.1. [ 20 ] Let G be a graph with a prime decomposition (B_{λ})_{λ<σ}. G is chordal if and only if every B_{λ} is a clique in G.

A typical application of Dirac’s theorem would be to prove that some property which holds trivially for complete graphs extends to all chordal graphs, by showing that it is preserved in the process of pasting graphs together along simplices. To consider just one example, note that perfection is such a property; a graph is perfect if the chromatic number of every induced subgraph equals the order of the largest clique in that subgraph. Therefore all finite chordal graphs are perfect. Since infinite graphs without infinite simplices also have prime decompositions, we even have the following result, which answers a question of Wagon [ 70 ]:

Theorem 3.2. [ 38 ] Every chordal graph not containing an infinite simplex is perfect.

(We remark that chordal graphs containing infinite simplices need not be perfect; see [ 70 ] for an example of R. Laver.)

Chordality is certainly a rather restrictive graph property—a fact clearly reflected in the uniformity of structure imposed on chordal graphs by Theorem 3.1. We may therefore expect that if we slightly relax its defining condition, the graphs we obtain can still be described in terms of their simplicial decompositions.

We present two results of this kind. The first of these is due to Gallai. Call a k-cycle C in a graph G triangulated if it has k − 3 pairwise non-crossing chords in G. (Two chords e_{1}, e_{2} of C cross if C can be written as C = x_{1} … x_{k} such that e_{1} = x_{i_{1}}x_{j_{1}}, e_{2} = x_{i_{2}}x_{j_{2}} and i_{1} < i_{2} < j_{1} < j_{2}; it is easily seen that a k-cycle can have at most k − 3 pairwise non-crossing chords.) A straightforward induction shows that a graph is chordal if and only if each of its cycles is triangulated. The property P_{1} that every odd cycle in a graph is triangulated is therefore a natural weakening of chordality. (Moreover, as is easily seen, this property is equivalent to the seemingly weaker one that every odd cycle of length at least 5 has two non-crossing chords.)

Gallai [ 28 ] proved that the simplicial primes among these graphs (i.e., those graphs in P_{1} that have no separating simplex) are of only two possible types: a simplex completely joined to a complete multipartite graph (in the notation of [ 3 ], a graph of the form K_{r} + K(s_{1}, …, s_{t})),^{1} or a simplex completely joined to a 2-connected bipartite graph. In both cases, either part of the sum may be empty.

Conversely, the union G_{1} ∪ G_{2} of two P_{1}-graphs identified along a common simplex is not necessarily again in P_{1}; the simplest counterexample is a C_{4} identified with a K_{3} along a K_{2}. However, it is easily checked that any such union which avoids joining an induced even cycle to a triangle in this way will be in P_{1}: an odd cycle C of G_{1} ∪ G_{2} that is in neither G_{i} has at least two non-crossing chords. We therefore arrive at the following characterization of P_{1}:

Theorem 3.3. Let G be a finite graph with a prime decomposition (B_{λ})_{λ<σ}. Then the following assertions are equivalent:

(i) Every odd cycle in G is triangulated.

(ii) Each factor B_{λ} is of the form K_{r} + K(s_{1}, …, s_{t}) or of the form K_{r} + H, where H is a bipartite graph. Furthermore, if μ < σ, e ^{∈} E(S_{μ}), { G_{1}, G_{2} } = { G|_{μ}, B_{μ} }, and e lies on a triangle of G_{1}, then e does not lie on an even induced cycle in G_{2}.

Let us now turn to the second result generalizing chordal graphs. The property P_{2} it describes is readily observed in planar triangulations: every induced cycle of length at least 4 separates the graph, but no proper (induced) subgraph of the cycle does. Clearly all chordal graphs have this property too, simply because they contain no such cycles. The question to what extent planar triangulations and chordal graphs are unique with this property is answered by the following theorem:

Theorem 3.4. [ 12 ] A finite graph has property P_{2} if and only if each of its simplicial prime factors is complete or maximally planar and every simplex of attachment contained in a non-complete factor has order 3 or 4.

A subspecies of the chordal graphs that has attracted much attention are the interval graphs, graphs that can be represented as intersection graphs of intervals on the real line. (The intersection graph of a family of sets has these sets as its vertices, and two sets are adjacent if and only if their intersection is non-empty.) Interval graphs are clearly chordal, and their simplicial decompositions into primes can be neatly identified among those described in Theorem 3.1.

1 Several authors have misquoted this type as merely the K(s_{1}, …, s_{t}), without the added K_{r}; there is even an entire paper investigating the (misconceived) ‘Gallai graphs’ arising from these primes.

Call a finite simplicial decomposition (B_{r})_{r≤s} of a graph G consecutive if S_{r} ⊂ B_{r−1} for every r ≤ s. The following description of finite interval graphs was first formulated by Halin [ 41 ]; however, it is related to an earlier characterization in terms of incidence matrices, due to Fulkerson and Gross [ 27 ].

Theorem 3.5. A finite graph is an interval graph if and only if it admits a consecutive simplicial decomposition into its cliques.

Of course, the linear arrangement of the cliques in an interval graph is not surprising: since real intervals have the Helly property (finitely many pairwise intersecting intervals have a non-empty overall intersection), every clique can be labelled by a real number contained in all its intervals, and the cliques inherit the natural order of their lables. Conversely, an interval representation of a graph G given as a consecutive union of cliques C_{1}, … C_{n} is also readily reobtained: for each vertex v ^{∈} G let I(v) be the real convex hull of the set { i | v ^{∈} C_{i} } of consecutive integers.

Theorem 3.5 can be used to derive other known criteria for interval graphs without much effort; see for example [ 39 ] for a proof of Gilmore and Hoffman’s characterization [ 30 ] (‘G is chordal, and its complement is a comparability graph’), or [ 41 ] for a short proof of the characterization due to Lekkerkerker and Boland [ 55 ] (‘G is chordal and contains no “asteroidal triple”’). Moreover, we have the following:

Corollary 3.6. [ 41 ] A graph G is an interval graph if and only if among any three cliques of G there is one which separates the other two.

Note that Corollary 3.6 is still true for infinite graphs; its proof is immediate from an adaptation of Theorem 3.5 to the infinite case.

We finally mention another subspecies of the chordal graphs, which is similar to interval graphs but not quite as restricted: the tree-representable graphs. A graph is treerepresentable if it is isomorphic to the intersection graph of a family of subtrees of some tree. Again, tree-representable graphs are clearly chordal. In fact, the finite tree-repre-sentable graphs coincide with the finite chordal graphs, a result independently proved by Buneman [ 4 ] and Gavril [ 29 ].

The problem of identifying the infinite tree-representable graphs however is much deeper, and it is one which leads straight into simplicial decomposition theory proper:

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

Or in other words (by Theorem 3.1), a graph is tree-representable if and only if it has a simplicial tree-decomposition into its cliques. Reobtaining a tree-representation of a graph G given in terms of such a decomposition F = (B_{λ})_{λ<σ} is completely analogous to the interval case: for each vertex v ^{∈} G the factors B_{λ} containing v span a subtree T_{v} of the decomposition tree T_{F} (G), and clearly two of these subtrees T_{v} and T_{w} intersect if and only if v and w are in a common clique of G, that is, if and only if v and w are adjacent.

The proof of Theorem 3.7 is already quite involved—it uses the notion of ends of a tree in order to adapt the Helly property of finite systems of subtrees to the infinite case—, and the result certainly gives a satisfactory description of any graph known to be tree-representable. Yet it does not offer much help for deciding whether a given graph is tree-representable, at least if we have problems decomposing it into primes and are not sure whether the desired decomposition exists. This problem however, to determine the graphs that admit a simplicial tree-decomposition (or indeed any simplicial decomposition) into primes, is still unsolved—and it is as hard for chordal graphs only as it is for arbitrary graphs.

The countable case of this problem however has recently been settled (see [ 13 ] and [ 14 ], or [ 16 ] for an overview), and we have the following corollary for tree-decompositions:

Theorem 3.8. [ 15 ] For a 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 of two specified graphs is its simplicial minor.

(For definitions of a simplicial minor and the two forbidden graphs see any of the given references.)

4. Infinite Graphs

In this section we consider applications of simplicial decompositions to problems in purely infinite graph theory. The applications are based on two theorems: one, due to Diestel, Halin and Vogler, which relates homomorphism and subdivision bases (see Section 1) to universal graphs, and another, due to Halin, which concerns decompositions of uncountable graphs into smaller factors. The axiom of choice will be assumed throughout this section.

For our discussion of universal graphs let us assume that all graphs considered are countable. When G is a class of graphs and G^{∗} ^{∈} G, call G^{∗} (strongly) universal in G if G^{∗} contains a copy of every graph G ^{∈} G as a subgraph (as an induced subgraph). Universal graphs were introduced by Rado [ 60 ], who constructed a strongly universal graph R for the class of all countable graphs. (Although Rado’s construction is explicit, we remark that R is isomorphic to the countably infinite random graph which occurs with probability one when the edges are chosen independently with probability 1/2.)

If G is a given monotone decreasing graph property (i.e., if H ⊂ G ^{∈} G implies H ^{∈} G) and G^{∗} is universal in G, then the subgraphs of G^{∗} are precisely the graphs in G. Thus, by constructing a universal graph for such a property G it may be possible to describe G ‘in a nutshell’. This hope has led several authors ([ 59 ], [ 52 ], [ 10 ]) to investigate which properties have universal graphs, though often with negative results. If G is given by excluded minors, however, it is often possible to use the homomorphism bases of Table 1 to construct a universal graph: all we have to do is paste the graphs of the base together in a sufficiently general way, allowing for embeddings of any graph with a decomposition into base elements that conforms to the given rules. In this manner universal graphs can be constructed for most of the classes G(HX) where X is one of the planar excluded minors listed in Table 1 [ 25, 10 ].

To prove that a given class G does not contain a universal graph is usually not an easy matter; such negative results can be found e.g. in [ 59 ], [ 52 ] and [ 10 ]. However the following theorem, proved in [ 9 ] but essentially already contained in [ 25 ], allows us to draw on existing decomposition results for excluded minor properties, and thereby to derive easily a large number of negative universal graph theorems.

Theorem 4.1. Let X be a set of finite graphs, and let G = G(HX) or G = G(TX). If the homomorphism base (or subdivision base, respectively) of G is uncountable, then G contains no universal graph.

As a consequence of Theorem 4.1 we immediately see that none of the classes G(HX) has a universal graph where X is any of the non-planar excluded minors listed in Table 1. Moreover, there is no universal planar graph (consider the homomorphism base for X = { K_{5}, K_{3,3} }), a result originally due to Pach [ 59 ].

We finally mention that the converse of Theorem 4.1 does not hold: there are classes G(HX) that have no universal graph but a countable, or even finite, homomorphism base [ 25 ].

We now turn to applications of simplicial decompositions to uncountable graphs. All these applications are consequences of the following fundamental decomposition theorem due to Halin. Given two vertices x, y of a graph G, let us write μ_{G}(x, y) for the Menger number of a and b in G, the supremum (in fact, the maximum) of all cardinals m such that G contains m independent x–y paths.

Theorem 4.2. [ 37, 17 ] Let G be a graph with |G| ≥ a > ℵ_{0} for some regular cardinal a. Suppose that G ⊅ K_{a}, and that μ_{G}(x, y) < a whenever x and y are non-adjacent vertices of G. Then G admits a simplicial decomposition F = (B_{λ})_{λ<σ}, where σ is the initial ordinal of |G| and |B_{λ}| < a for all λ < σ. F can be chosen in such a way that, for each μ < σ, S|_{μ} does not separate B_{μ} and every vertex of S|_{μ} has a neighbour in B_{μ}\S|_{μ}.

Theorem 4.2 can often be used to extend results for countable graphs to uncountable ones. We give three examples of this: an infinite version of Hadwiger’s conjecture, a result extending a theorem of Jung [ 51 ] on the existence of certain spanning trees, and a theorem concerning the so-called ends of a graph. More such applications can be found in [ 36, 37 ].

If G has chromatic number ℵ_{0}, then G ⊃ TK_{r} for every finite r. Indeed, if G ⊅ TK_{r} and r ^{∈} ℕ, then χ(G′) ≤ s for all finite G′ ⊂ G and some s depending on r [ 50 ]; by a well-known theorem of de Bruijn and Erdős [ 24 ] this implies that χ(G) ≤ s. The following theorem extends this result to arbitrary infinite graphs:

Theorem 4.3. [ 36 ] If G has chromatic number χ(G) ≥ ℵ_{0}, then G ⊃ TK_{a} for every a < χ(G).

We remark that Theorem 4.3 is sharp: G need not contain a TK_{χ(G)}, even if χ(G) is a successor cardinal [ 39, Ch. X.10.7 ].

Call a rooted spanning tree T of a graph G normal if every pair of adjacent vertices of G is comparable in the partial order on V (G) induced by T. Jung [ 51 ] proved that every countable connected graph contains a normal rooted spanning tree. Using Theorem 4.2, this result can be extended as follows:

Theorem 4.4. [ 37 ] Every connected graph not containing a TK_{ℵ_{0}} has a normal rooted spanning tree.

In fact, Halin conjectured that the condition of not containing a TK_{ℵ_{0}} can be weakened further:

Conjecture. [ 37 ] A connected graph G has a normal rooted spanning tree if and only if every uncountable set X ⊂ V (G) contains vertices x, y for which μ_{G}(x, y) is finite.

A similar extension from the countable to the uncountable produced a step forward towards a solution of the following long-standing problem. Call two rays (one-way infinite paths) P, Q in a connected infinite graph G end-equivalent if there exists a ray R ⊂ G which meets both P and Q infinitely often. Let E(G) denote the set of the corresponding equivalence classes, the ends of G. For example, the 2-way infinite ladder has two ends, the infinite grid ℤ × ℤ has one end, and the dyadic tree has 2^{ℵ_{0}} ends.

If T is a spanning tree of G and P, Q are end-equivalent rays in T, then clearly P and Q are also equivalent in G. We therefore have a natural map η : E(T) → E(G) mapping each end of T to the end of G containing it. In general, η need be neither 1–1 nor onto; if it is both, then T is called end-faithful. The following question was raised by Halin in 1964:

Problem. [ 43 ] Does every infinite connected graph have an end-faithful spanning tree?

For countable graphs, such a tree was already constructed as the main result in Halin [ 43 ]. Using Theorem 4.2, this construction can again be extended:

Theorem 4.5. [ 18 ] Every connected graph not containing a TK_{ℵ_{0}} has an end-faithful spanning tree.

The basic idea in the proofs of Theorems 4.4 and 4.5 is to decompose a given graph G into countable factors by Theorem 4.2, use the countable version of the theorem to find admissible spanning trees in each of the factors, and to combine these spanning trees into one of G. However, in order to avoid the rather restrictive condition on the Menger numbers in Theorem 4.2, Theorem 4.2 is applied not to G itself but to a slight modification of G: its ℵ_{1}-closure.

The a-closure [ G]_{a} of a graph G is obtained by adding all edges between non-adjacent vertices x, y with μ_{G}(x, y) ≥ a. It is not difficult to show that in the a-closure of a graph the Menger number of any two non-adjacent vertices is less than a, as required for Theorem 4.2. Moreover, the edges added in the closure operation will not jeopardize the other condition of Theorem 4.2, that G ⊅ K_{a}, since a new K_{a} can only be created if G already contained a TK_{a}:

Theorem 4.6. [ 36, 17 ] For any graph G and any infinite cardinal a the following are equivalent:

(i) [ G]_{a} ⊃ K_{a};  (ii) [ G]_{a} ⊃ TK_{a};  (iii) G ⊃ TK_{a}.

Used in conjunction with Theorem 4.6, Theorem 4.2 becomes a very powerful tool indeed for decomposing infinite graphs into smaller factors.

We conclude this section with another application of these two theorems, which generalizes a result of Dirac [ 22, 23 ].

Theorem 4.7. [ 37 ] Let G be an n-connected graph (n ^{∈} ℕ), and suppose that a is a regular cardinal with |G| ≥ a > ℵ_{0}. Then G ⊃ TK_{n,a}.

Corollary 4.8. If an uncountable graph G is n-connected, n ^{∈} ℕ, then G ⊃ TK_{n}.

5. Related Decompositions

Among the motivations suggested in the introduction of this paper for decomposing graphs into simplicial factors was the prospect of being able to ‘lift assertions about the factors to similar assertions about the whole graph’; k-colourability was given as an example to illustrate the idea. The value of a particular kind of decomposition for this purpose clearly depends on two features of the graph property under investigation. Firstly, the property must be wholly or at least to a controllable extent preserved in the pasting operation, and secondly, it must be easier to investigate the factors of the graph than the graph itself. However, these two objectives obviously work against each other: the more specificly we define our attachment rule, the fewer graphs will be decomposable, and the larger the primes we get—and vice versa. Finding the right kind of decomposition for a given problem is therefore a task of striking a balance.

As was illustrated (and to some degree explained) in Section 1, simplicial decompositions seem to be just the right kind of decomposition for investigating minor-closed properties, and properties defined in terms of forbidden subdivisions. In general, however, the requirement (S2) that all attachment graphs be simplices seems to be rather on the strict side. If one focusses on monotone increasing classes of attachment graphs (and there seem to be reasons for doing so), simplicial decompositions are even an extreme case, based on the smallest possible class of attachment graphs. And indeed, while quite a few graph properties are compatible with attachment along a simplex (i.e., can be lifted from simplicial factors to the whole graph), simplicial decompositions do tend to leave rather large primes, which are often not fewer in number or simpler in structure than arbitrary graphs with that property. The k-colourable graphs are again a case in point.

Halin [ 40 ] suggested to take account of this problem by relaxing condition (S2) in the definition of simplicial decompositions if appropriate, while keeping the tree structure of the decomposition by imposing (S4). This, together with a few additional constraints, would ensure that the structural properties of the decompositions obtained would be similar to simplicial ones, enabling us to transfer some of the existing theory. However, if we place the emphasis firmly on decomposability to a high degree, keeping the tree structure seems unnecessarily restrictive: it may prevent us from decomposing a factor further, even if it has a separator that would be admissible as an attachment graph (an example will be given below).

The simplest way to ensure maximum decomposability (with respect to a fixed class P of admissible attachment graphs) is to use as an attachment rule the direct reversal of the process of successive separation. For properties P and G of finite graphs let us define the P-sum of graphs in G recursively:

(1) Every G ^{∈} G is a P-sum of graphs in G;

(2) If G, G′ are P-sums of graphs in G and G ∩ G′ ^{∈} P, then G ∪ G′ is a P-sum of graphs in G.

For P_{k} = { G : |G| = k } and P_{≤k} = { G : |G| ≤ k }, we abbreviate ‘P_{k}-sum’ to ‘ksum’, ‘P_{≤k}-sum’ to ‘(≤ k)-sum’, ‘(P ∩ P_{k})-sum’ to ‘P-k-sum’ and so on. Moreover, we shall loosely speak of simplicial sums, connected sums etc. if P is the property of being complete, connected etc..

Using well-known facts about simplicial decompositions it is not difficult to show that any simplicial sum of certain graphs admits a simplicial decomposition into precisely these graphs as factors (provided only that none of them is contained in another), and with precisely those simplices as simplices of attachment that were used as attachment graphs for building the sum. For a simplicial sum we may therefore usually assume without loss of generality that it was obtained by adding only one factor at a time.

For other sums however this is not the case. As an example, consider the graph shown in Figure 2: it is a connected 3-sum of four K_{4}’s, obtained by first pasting the K_{4}’s together in pairs along triangles and then joining the two arising K_{5}^{−}’s along a common path of order 3. This graph cannot be obtained as a 3-sum of K_{4}’s in any other way.

FIGURE 2. A connected 3-sum of K_{4}’s

Connected sums are used in a recent paper of Duchet, Las Vergnas and Meyniel [ 26 ] to describe two interesting graph properties: ‘well-connectedness’ and ‘null-homotopy’. A graph G is well-connected if every minimal relative separator is (non-empty and) connected, and G is null-homotopic if every algebraic cycle of G is the sum (mod 2) of triangles. Both these properties are compatible with connected summing: if G = G′ ∪ G′′ where G′ and G′′ are well-connected (null-homotopic) and G′ ∩ G′′ is connected, then G is well-connected (null-homotopic). Using Wagner’s characterization of the finite graphs without a K_{5} minor (see Table 1), Duchet, Las Vergnas and Meyniel obtain the following result:

Theorem 5.1. [ 26 ] For a finite connected graph G ^{∈} G(HK_{5}) the following statements are equivalent:

(i) G is null-homotopic; (ii) G is well-connected; (iii) G is a connected (≤ 3)-sum of disc-triangulations.

(A disc-triangulation is a plane graph in which at most one face is not a triangle.) It is interesting to note that if G is required to be planar, the connected 3-sums in Theorem 5.1 can be replaced with simplicial 3-sums [ 26 ].

Using other homomorphism bases from Table 1, Theorem 5.1 can be extended as follows:

Theorem 5.2. If G is a finite connected graph from any of the classes G(HK_{3,3}), G(HW_{1,5}), G(HL) or G(H(C_{3} × K_{2})), the following statements are equivalent:

(i) G is null-homotopic; (ii) G is well-connected; (iii) G is a connected (≤ 3)-sum of disc-triangulations and copies of K_{5}. If G ^{∈} G(H(C_{3} × K_{2})), the disc-triangulations in (iii) can be chosen as wheels, triangles, K_{5}^{−}’s or K_{2}’s.

An infinite analogue to k-sums can be obtained from the definition of simplicial decompositions by replacing (S2) with a condition on the order of the attachment graphs. Given an infinite cardinal a and a graph G, call a family (B_{λ})_{λ<σ} of induced subgraphs of G an a-decomposition of G if it satisfies (S1), (S3) and (S_{a}2) Each subgraph (⋃_{λ<μ} B_{λ}) ∩ B_{μ} =: S_{μ} has order < a (0 < μ < σ), (S_{a}5) Every graph ⋃_{λ<μ} B_{λ} is an induced subgraph of G (0 < μ < σ). As a consequence of Halin’s decomposition theorem 4.2 and Theorem 4.6 we then have the following remarkable result:

Theorem 5.4. If G is a graph, a is a regular uncountable cardinal and G ⊅ TK_{a}, then G has an a-decomposition (B_{λ})_{λ<σ} into factors of order < a. This decomposition can be chosen in such a way that, for every μ < σ, S_{μ} separates (⋃_{λ<μ} B_{λ}) \ S_{μ} from B_{μ}\S_{μ} in G.

Conversely, a graph with a decomposition as in Theorem 5.4 may well contain a TK_{a}; for example, a TK_{a} in which every edge has been subdivided once has such a decomposition. No characterization of the graphs admitting an a-decomposition into factors of order < a is known, for any a.

6. Algorithmic Aspects of Simplicial Decompositions

Let us finally mention some algorithmic aspects of simplicial decompositions. Whitesides [ 71 ] and Tarjan [ 63 ] were the first to propose algorithms that decompose a given finite graph into simplicial factors. Examples of how to use these algorithms to tackle otherwise NP-complete problems in graph theory are also found in [ 63 ] and [ 71 ]. The problems considered are vertex colouring [ 63, 71 ], ‘minimizing the fill-in caused by Gaussian elimination’ [ 63 ], finding a clique (or a stable set of vertices) of largest weight [ 63, 71 ], and finding a maximal weight clique or stable set cover [ 71 ]. A refined version of Tarjan’s algorithm which finds the unique set of simplicial primes of a finite graph is due to Leimer [ 54 ]. (Tarjan’s original algorithm ends with a set of subgraphs containing the prime factors as well as some simplices of attachment.) Both algorithms run in O(nm) time, where n and m are the numbers of vertices and of edges in the graph, respectively. A parallel algorithm for the same problem was recently proposed by Dahlhaus (private communication). This algorithm runs in O(log^{2} n) time on O(n^{4}) processors.

Algorithmic applications of simplicial decompositions to problems in statistics are considered by Lauritzen and Spiegelhalter [ 56 ]. Decompositions of chordal graphs into their cliques (as discussed in Section 3) have applications to problems in areas as diverse as measure theory and database schemes; see Lauritzen, Speed and Vijayan [ 57 ] and Beeri et al. [ 6, 7 ].

Acknowledgement

I would like to thank Leif Jørgensen for pointing out an error in the discussion of homomorphism bases in an earlier version of this article.

References

[ 1 ] Th. Andreae, On a pursuit game played on graphs for which a minor is excluded, J. Combin. Theory B

41 (1986), 37–47. [ 2 ] S. Arnborg, D. G. Corneil and A. Proskurowski, Forbidden minors characterization of partial 3-trees,

Discrete Math. (to appear). [ 3 ] B. Bollobás, Extremal Graph Theory, Academic Press, London 1978. [ 4 ] P. Buneman, A characterization of rigid circuit graphs, Discrete Math. 9 (1974), 205–212. [ 5 ] B. Bollobás and P. Erdős, On some extremal problems in graph theory (in Hungarian), Math.

Lapok 13 (1962), 143–153. [ 6 ] C. Beeri, R. Fagin, D. Maier, A. Mendelzon, J. Ullman and M. Yannakakis, Properties of acyclic

database schemes, in: Proc. 13th Annual ACM Symposium on the Theory of Computing, Milwaukee, J. Assoc. Comput. Mach., New York 1981.

[ 7 ] C. Beeri, R. Fagin, D. Maier and M. Yannakakis, On the desirability of acyclic database schemes,

J. Assoc. Comput. Mach. 30 (1983), 479–513. [ 8 ] V. Chvátal, Star-cutsets and perfect graphs, J. Combin. Theory B 39 (1985), 189–199. [ 9 ] R. Diestel, Simplicial decompositions and universal graphs, Ph.D. Thesis, University of Cambridge

(England), 1986. [ 10 ] R. Diestel, On universal graphs with forbidden topological subgraphs, Europ. J. Combinatorics 6

(1985), 175–182. [ 11 ] R. Diestel, On the problem of finding small subdivision and homomorphism bases for classes of

countable graphs, Discrete Math. 55 (1985), 21–33. [ 12 ] R. Diestel, A separation property of planar triangulations, J. Graph Theory 11 (1987), 43–52. [ 13 ] R. Diestel, Simplicial tree-decompositions of infinite graphs I–III, submitted. [ 14 ] R. Diestel, Simplicial minors and decompositions of graphs, Math. Proc. Camb. Phil. Soc. (to appear). [ 15 ] R. Diestel, Tree-decompositions, tree-representability and chordal graphs, Discrete Math. (to ap-

pear). [ 16 ] R. Diestel, Simplicial decompositions, tree-decompositions and graph minors, Ars Combinatoria (to

appear). [ 17 ] R. Diestel, Decompositions of infinite graphs into small induced subgraphs, submitted.

[ 18 ] R. Diestel, On end-faithful spanning trees in infinite graphs, submitted. [ 19 ] R. Diestel, Decompositions in graph theory, Oxford University Press, in preparation. [ 20 ] G. A. Dirac, On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg 25 (1961), 71–76. [ 21 ] G. A. Dirac, Homomorphism theorems for graphs, Math. Ann. 153 (1964), 69–80. [ 22 ] G. A. Dirac, Structural properties and circuits in graphs, Proc. 5th British Comb. Conf. (Aberdeen,

1975), Congr. Num. bf 15 (1975), 135–140. [ 23 ] G. A. Dirac, Cardinal-determining subgraphs of infinite graphs, Aarhus Universitet, Matematisk In-

stitut, Preprint Series 27 (1976/77). [ 24 ] N. G. de Bruijn and P. Erdős, A colour problem for infinite graphs and a problem in the theory of

relations, Indag. Math. 13 (1951), 371–373. [ 25 ] R. Diestel, R. Halin and W. Vogler, Some remarks on universal graphs, Combinatorica 5 (1985), 283–

293. [ 26 ] P. Duchet, M. Las Vergnas and H. Meyniel, Connected cutsets of a graph and triangle bases of the

cycle space, Discrete Math. (to appear). [ 27 ] D. R. Fulkerson and O. A. Gross, Incidence matrices and interval graphs, Pacific J. Math. 15 (1965),

835–855. [ 28 ] T. Gallai, Graphen mit triangulierbaren ungeraden Vierecken, Magyar Tud. Akad. Mat. Kut. Intéz.

Közl. (= Publ. Mat. Inst. Hung. Acad. Sci.) 7 (1962), 3–36. [ 29 ] F. Gavril, The intersection graphs of subtrees in trees are exactly the chordal graphs, J. Combin.

Theory B 16 (1974), 47–56. [ 30 ] P. C. Gilmore and A. J. Hoffman, A characterization of comparability graphs and interval graphs,

Canad. J. Math. 16 (1964), 539–548. [ 31 ] R. Halin, Über einen graphentheoretischen Basisbegriff und seine Anwendung auf Färbungsprobleme,

Diss. Köln, 1962. [ 32 ] R. Halin, Über einen Satz von K. Wagner zum Vierfarbenproblem, Math. Ann. 153 (1964), 47–62. [ 33 ] R. Halin, Simpliziale Zerfällungen beliebiger (endlicher oder unendlicher) Graphen, Math. Ann. 156

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

(1967), 46–78. [ 35 ] R. Halin, Ein Zerlegungssatz für unendliche Graphen und seine Anwendung auf Homomorphiebasen,

Math. Nachr. 33 (1967), 91–105. [ 36 ] R. Halin, Unterteilungen vollständiger Graphen in Graphen mit unendlicher chromatischer Zahl, Abh.

Math. Sem. Univ. Hamburg 31 (1967), 156–165. [ 37 ] R. Halin, Simplicial decompositions of infinite graphs, in: (B. Bollobás, ed.) Advances in Graph

Theory (Annals of Discrete Mathematics 3), North-Holland Publ. Co., Amsterdam/London 1978. [ 38 ] R. Halin, A note on infinite triangulated graphs, Discrete Math. 31 (1980), 325–326. [ 39 ] R. Halin, Graphentheorie II, Wissenschaftliche Buchgesellschaft, Darmstadt 1981. [ 40 ] R. Halin, Simplicial decompositions, some new aspects and applications, in: (B. Bollobás, ed.) Graph

Theory and Combinatorics (Annals of Discrete Mathematics 13), North-Holland Publ. Co., Amsterdam/London 1982.

[ 41 ] R. Halin, Some remarks on interval graphs, Combinatorica 2 (1982), 297–304. [ 42 ] R. Halin, On the representation of triangulated graphs in trees, Europ. J. Combinatorics 5 (1984),

23–28. [ 43 ] R. Halin, Über unendliche Wege in Graphen, Math. Ann. 157 (1964), 125–137. [ 44 ] R. Halin and K. Wagner, Homomorphiebasen von Graphenmengen, Math. Ann. 147 (1962), 126–142.

[ 45 ] I. T. Jakobsen, A homomorphism theorem with an application to the conjecture of Hadwiger, Studia

Sci. Math. Hungar. 6 (1971), 151–160. [ 46 ] I. T. Jakobsen, On certain homomorphism properties I, Math. Scand. 31 (1972), 379–404. [ 47 ] I. T. Jakobsen, On certain homomorphism properties II, Math. Scand. 52 (1983), 229–261. [ 48 ] L. K. Jørgensen, Extremal graphs for contractions to K_{7}, Ars Combinatoria (to appear) [ 49 ] L. K. Jørgensen, in preparation. [ 50 ] H. A. Jung, Anwendung einer Methode von K. Wagner bei Färbungsproblemen für Graphen, Math.

Ann. 161 (1965), 325–326. [ 51 ] H. A. Jung, Wurzelbäume und unendliche Wege in Graphen, Math. Nachr. 41 (1969), 1–22. [ 52 ] P. Komjáth and J. Pach, Universal graphs without large bipartite subgraphs, Mathematika 31 (1984),

282–290. [ 53 ] H.-G. Leimer, Triangulated graphs with marked vertices, Proceedings of the Conference in Memory

of G. A. Dirac, Annals of Discrete Mathematics, to appear. [ 54 ] H.-G. Leimer, Optimal decomposition by complete separators, Discrete Math. (to appear). [ 55 ] C. Lekkerkerker and J. Boland, Representation of a finite graph by a set of intervals on the real line,

Fund. Math. 51 (1962), 45–64. [ 56 ] S. L. Lauritzen and D. J. Spiegelhalter, Local computations with probabilities on graphical structures

and their application to expert systems, J. R. Statist. Soc. B 55 (1988), to appear. [ 57 ] S. L. Lauritzen, T. P. Speed and K. Vijayan, Decomposable graphs and hypergraphs, J. Austral. Math.

Soc. A 36 (1984), 12–19. [ 58 ] R. Nowakowski and P. Winkler, Vertex-to-vertex pursuit in a graph, Discrete Math. 43 (1983), 235–

239. [ 59 ] J. Pach, A problem of Ulam on planar graphs, Europ. J. Combinatorics 2 (1981), 357–361. [ 60 ] R. Rado, Universal graphs and universal functions, Acta Arith. 9 (1964), 331–340. [ 61 ] N. Robertson and P. D. Seymour, Graph minors I–XVIII, J. Combin. Theory B (to appear). [ 62 ] N. Robertson and P. D. Seymour, Generalizing Kuratowski’s Theorem, Proceedings of the fifteenth

Southeastern conference on combinatorics, graph theory and computing (Baton Rouge, 1984), Congr. Num. 45 (1984), 129–138.

[ 63 ] R. E. Tarjan, Decomposition by clique separators, Discrete Math. 55 (1985), 221–232. [ 64 ] C. Thomassen, Some homomorphism properties of graphs, Math. Nachr. 64 (1974), 119–133. [ 65 ] K. Truemper, A decomposition theory for matroids IV: decompositions of graphs, J. Combin. The-

ory B (to appear). [ 66 ] C. Thomassen and B. Toft, Non-separating induced cycles in graphs, J. Combin. Theory B 31 (1981),

199–224. [ 67 ] K. Wagner, Über eine Eigenschaft der ebenen Komplexe, Math. Ann. 114 (1937), 570–590. [ 68 ] K. Wagner, Über eine Erweiterung eines Satzes von Kuratowski, Deutsche Math. 2 (1937), 280–285. [ 69 ] K. Wagner, Bemerkungen zu Hadwigers Vermutung, Math. Ann. 141 (1960), 433–451. [ 70 ] S. Wagon, Infinite triangulated graphs, Discrete Math. 22 (1978), 183–189. [ 71 ] S. H. Whitesides, A method for solving certain graph recognition and optimization problems, in:

(C. Berge and V. Chvátal, eds.) Topics on Perfect Graphs (Annals of Discrete Mathematics 21), North-Holland Publ. Co., Amsterdam 1984.

Department of Pure Mathematics 16 Mill Lane Cambridge CB2 1SB England