Tree Representations of Kn,n

-
E1 241
  1. Home
  2. Events
  3. Tree Representations of Kn,n


Speaker

Jozef Skokan
Department of Mathematics, University of Illinois at Urbana-Champaign
http://www.maths.lse.ac.uk/Personal/jozef/



Description

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.

Tags: