On the representation of triangulation graphs in trees
type: Item
instance of: scholarly article
title: On the representation of triangulation graphs in trees
zbMATH Open document ID: 0541.05049
DOI: 10.1016/S0195-6698(84)80014-1
published in: European Journal of Combinatorics
publication date: 1984-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 3859173
zbMATH Keywords: intersection graph
zbMATH Keywords: tree-representable graphs
zbMATH Keywords: simplicial decompositions
author: Rudolf Halin
MaRDI profile type: Publication
cites work: A characterisation of rigid circuit graphs
cites work: On rigid circuit graphs
cites work: The intersection graphs of subtrees in trees are exactly the chordal graphs
cites work: Q3328583
cites work: Q5609148
cites work: Über simpliziale Zerfällungen beliebiger (endlicher oder unendlicher) Graphen
cites work: Über unendliche Wege in Graphen
cites work: Q3929755
cites work: Representations of chordal graphs as subtrees of a tree
description: scientific article; zbMATH DE number 3859173