Tree representations of graphs

Nancy Eaton, Zoltán Füredi, Alexandr V. Kostochka, Jozef Skokan

Research output: Contribution to journalArticlepeer-review

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 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.

Original languageEnglish (US)
Pages (from-to)1087-1098
Number of pages12
JournalEuropean Journal of Combinatorics
Volume28
Issue number4
DOIs
StatePublished - May 2007

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Tree representations of graphs'. Together they form a unique fingerprint.

Cite this