Department of
Applied
Mathematics

Circular choosability of graphs

Jean-Sébastien Sereni

Abstract

The notion of circular choosability is a natural list variant of the ciruclar chromatic number, introduced by Mohar and Zhu. Its definition might make it look unhandy to work with at first glance, yet it is an interesting notion, with a lot of (fundamental) open problems. My main aim in this talk will be to state the definition and give such open problems. I will also review some of the results we obtain. For instance, I will prove that the circular choice number of any graph G of n vertices is O( ch(G) + ln n ), where ch(G) denotes the choice number of G. Planar graphs will be considered, in particular the supremum of the circular choice number over this class: perhaps counter-intuitively, this supremum lies between 6 and 8.

This is joint work with Frederic Havet, Ross Kang and Tobias Muller.