Premium
Representations of chordal graphs as subtrees of a tree
Author(s) -
Walter James R.
Publication year - 1978
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190020311
Subject(s) - chordal graph , combinatorics , citation , computer science , tree (set theory) , graph , mathematics , discrete mathematics , world wide web
In 1974, Buneman [ l ] and Gavril [2] independently showed that a connected graph G is isomorphic to the intersection graph of subtrees of a tree if and only if G is chordal. This result, which also appears in [5] , can be derived directly from a result of Lekkerkerker and Boland [4] , which states that a chordal graph has a simplicia1 point. We give a proof of this characterization and we conclude with an announcement of a criterion for a graph to be representable on Kl,3. In general, we follow the graph theoretic terminology of [3] .