TY - JOUR

T1 - Tree representations of graphs

AU - Eaton, Nancy

AU - Füredi, Zoltán

AU - Kostochka, Alexandr V.

AU - Skokan, Jozef

N1 - Funding Information:
Zoltán Füredi was supported in part by the Hungarian National Science Foundation under grant OTKA NK 62321 and by the National Science Foundation under grant DMS-0140692. Alexandr V. Kostochka was partially supported by National Science Foundation grants DMS-0099608 and DMS-0400498. Jozef Skokan was partially supported by National Science Foundation grant INT-0305793, by National Security Agency grant H98230-04-1-0035, by CNPq (Proc. 479882/2004–5), and by FAPESP (Proj. Temático–ProNEx Proc. FAPESP 2003/09925–5 and Proc. FAPESP 2004/15397–4).

PY - 2007/5

Y1 - 2007/5

N2 - 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 G is in the family [Δ, d, t] if there is a tree with maximum degree Δ and subtrees corresponding to the vertices of G such that each subtree has maximum degree at most d and two vertices of G are adjacent if and only if the subtrees corresponding to them have at least t common vertices. It is known that both [3, 3, 1] and [3, 3, 2] are equal to the family of chordal graphs. Furthermore, one can easily observe that every graph G belongs to [3, 3, t] for some t. Denote by t (G) the minimum t so that G ∈ [3, 3, t]. In this paper, we study t (G) and parameters 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 log n < tbip (n) ≤ 5 n1 / 3 log2 n and log (n / 2) < t (n) ≤ 20 n1 / 3 log2 n.

AB - 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 G is in the family [Δ, d, t] if there is a tree with maximum degree Δ and subtrees corresponding to the vertices of G such that each subtree has maximum degree at most d and two vertices of G are adjacent if and only if the subtrees corresponding to them have at least t common vertices. It is known that both [3, 3, 1] and [3, 3, 2] are equal to the family of chordal graphs. Furthermore, one can easily observe that every graph G belongs to [3, 3, t] for some t. Denote by t (G) the minimum t so that G ∈ [3, 3, t]. In this paper, we study t (G) and parameters 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 log n < tbip (n) ≤ 5 n1 / 3 log2 n and log (n / 2) < t (n) ≤ 20 n1 / 3 log2 n.

UR - http://www.scopus.com/inward/record.url?scp=33847680149&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33847680149&partnerID=8YFLogxK

U2 - 10.1016/j.ejc.2006.04.002

DO - 10.1016/j.ejc.2006.04.002

M3 - Article

AN - SCOPUS:33847680149

SN - 0195-6698

VL - 28

SP - 1087

EP - 1098

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

IS - 4

ER -