Jozef Skokan
(Department of Mathematics,
University of Illinois at Urbana-Champaign)
Tree Representations of Kn,n
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. A graph G is in the family [D,d,t]
if there is a tree with maximum degree D and subtrees corresponding
to the vertices of G such that each subtree has maximum degree at
most d and vertices of G are adjacent if and only if the subtrees
corresponding to them have at least t common vertices.
It is known that [3,3,1] and [3,3,2] both equal the family of chordal graphs.
Since a complete bipartite graph with partite sets of size at
least 2 is not chordal, we study the minimum t such that Kn,n
is in [3,3,t]. In this talk, we provide bounds for t in terms
of n and discuss
related problems.
This is joint work with N. Eaton, Z. Furedi, and A.V. Kostochka.
|