Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-24T12:39:29.435Z Has data issue: false hasContentIssue false
  • English
  • Français

Simplicial minors and decompositions of graphs

Published online by Cambridge University Press:  24 October 2008

Reinhard Diestel
Reinhard Diestel
Affiliation:
St. John's College, Cambridge
Get access Rights & Permissions [Opens in a new window]

Extract

The purpose of this paper is to give natural characterizations of the countable graphs that admit tree-decompositions or simplicial tree-decompositions into primes. Tree-decompositions were recently introduced by Robertson and Seymour in their series of papers on graph minors [7]. Simplicial tree-decompositions were first considered by Halin[6], being the most typical kind of ‘simplicial decomposition’ as introduced by Halin[5] in 1964. The problem of determining which infinite graphs admit a simplicial decomposition into primes has stood unresolved since then; a first solution for simplicial tree-decompositions was given in [2].

Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 103 , Issue 3 , May 1988 , pp. 409 - 426
Copyright
Copyright © Cambridge Philosophical Society 1988

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Diestel, R.. Simplicial tree-decompositions of infinite graphs I. (Submitted.)Google Scholar
[2]Diestel, R.. Simplicial tree-decompositions of infinite graphs II—the existence of prime decompositions. (Submitted.)Google Scholar
[3]Diestel, R.. Simplicial tree-decompositions of infinite graphs III—the uniqueness of prime decompositions. (Submitted.)Google Scholar
[4]Dirac, G. A.. Simplicial decompositions of infinite graphs. In Combinatorial, Conv. Roma 1983, Symposia Math. vol. 28 (1986), pp. 159–195.Google Scholar
[5]Halin, R.. Simpliziale Zerfällungen beliebiger (endlicher oder unendlicher) Graphen. Math. Ann. 156 (1964), 216–225.CrossRefGoogle Scholar
[6]Halin, R.. On the representation of triangulated graphs in trees. Europ. J. Combinatorics 5 (1984), 23–28.CrossRefGoogle Scholar
[7]Robertson, N. and Seymour, P. D.. Graph minors I-XVIII. J. Combin. Theory B (in the Press).Google Scholar
[8]Wagner, K.. Über eine Eigenschaft der ebenen Komplexe. Math. Ann. 114 (1937), 570–590.CrossRefGoogle Scholar