List-colouring Steiner triple systems
by
Martin Pei
University of Waterloo
Coauthors: Penny Haxell

We discuss the problem of list-colouring Steiner Triple Systems (STS), in relation to the (ordinary) colouring problem. The list chromatic spectrum of some admissible order is the set of all possible list-chromatic numbers for STS of this order. We prove that the lower bound on the list chromatic spectrum grows with the size of the STS. This is not true for the chromatic number as there exist 3-chromatic STS for all admissible orders. We also show that the list-chromatic number of an STS can be no more than a log factor times its chromatic number. Combining the two results give interesting bounds on the list chromatic spectrum, in particular we find a tight asymptotic range for the lower bound of the spectrum for large STS. This is joint work with Penny Haxell.

Date received: April 7, 2008