×

zbMATH — the first resource for mathematics

On the representation of triangulation graphs in trees. (English) Zbl 0541.05049
A graph G is said to be tree-representable if there exist a tree T and a family \(T_ i\) (\(i\in I)\) of subtrees of T such that G is isomorphic to the intersection graph of this family. It has been shown independently by several authors that if G is a finite graph then G is tree-representable if and only if G is chordal, i.e., no cycle of length at least 4 is an induced subgraph of G. It is not true that every infinite chordal graph is tree-representable. The author’s main result is a characterization of all tree-representable graphs, given by means of simplicial decompositions.
Reviewer: L.Lesniak

MSC:
05C75 Structural characterization of families of graphs
05C05 Trees
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Buneman, P., A characterization of rigid circuit graphs, Discrete math., 9, 205-212, (1974) · Zbl 0288.05128
[2] Dirac, G.A., On rigid circuit graphs, Abh. math. sem. univ. Hamburg, 25, 71-76, (1961) · Zbl 0098.14703
[3] Gavril, F., The intersection graphs of subtrees in trees are exactly the chordal graphs, J. combin. theory B, 16, 47-56, (1974) · Zbl 0266.05101
[4] Golumbic, M.C., Algorithmic graph theory and perfect graphs, (1980), Academic Press New York · Zbl 0541.05054
[5] Gyárfas, A.; Lehel, J., A Helly type problem in trees, (), 571-584, Coll. Math. Soc. J. Bolyai 4, North-Holland, Amsterdam
[6] Halin, R., Über simpliziale zerfällungen beliebiger (endlicher oder unendlicher) graphen, Math. ann., 156, 216-225, (1964) · Zbl 0125.11605
[7] Halin, R., Über unendliche wege in graphen, Math. ann., 157, 125-137, (1964) · Zbl 0125.11701
[8] Halin, R., Graphentheorie II, (1981), Wissenschaftliche Buchgesellschaft Darmstadt
[9] Walter, J.R., Representations of chordal graphs as subtrees of a tree, J. graph theory, 2, 265-267, (1978) · Zbl 0441.05022
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.