Tree representations of graphs

Abstract: A graph is chordal if and only if it is the intersection graph of some family of subtrees of a tree. Applying “tolerance” allows larger families of graphs to be represented by subtrees. A graph is in the family if there is a tree with maximum degree and subtrees corresponding to the vertices of such that each subtree has maximum degree at most and two vertices of are adjacent if and only if the subtrees corresponding to them have at least common vertices. It is known that both and are equal to the family of chordal graphs. Furthermore, one can easily observe that every graph belongs to for some . Denote by the minimum so that . In this paper, we study and parameters and In particular, our results imply that and . [Copyright &y& Elsevier]