Tree representations of graphs

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 GG is in the family [Δ,d,t] if there is a tree with maximum degree Δ and subtrees corresponding to the vertices of GG such that each subtree has maximum degree at most dd and two vertices of GG are adjacent if and only if the subtrees corresponding to them have at least tt common vertices.It is known that both [3,3,1][3,3,1] and [3,3,2][3,3,2] are equal to the family of chordal graphs. Furthermore, one can easily observe that every graph GG belongs to [3,3,t][3,3,t] for some tt. Denote by t(G)t(G) the minimum tt so that G∈[3,3,t]G∈[3,3,t]. In this paper, we study t(G)t(G) and parameters t(n)=min{t:G∈[3,3,t] for every G⊆Kn}t(n)=min{t:G∈[3,3,t] for every G⊆Kn} and tbip(n)=min{t:G∈[3,3,t] for every G⊆Kn,n}. In particular, our results imply that logn