Charles Explorer logo
🇬🇧

Circular Choosability

Publication at Faculty of Mathematics and Physics |
2009

Abstract

We study circular choosability, a notion recently introduced by Mohar and Zhu. First, we provide a negative answer to a question of Zhu about circular cliques.

We next prove that cch(G)=O(ch(G) ln|V(G)|) for every graph G. We investigate a generalization of circular choosability, the circular f-choosability, where f is a function of the degrees.

We also consider the circular choice number of planar graphs. Mohar asked for the value of tau:=sup{cch(G) : G is planar}, and we prove that tau is between 6 and 8, thereby providing a negative answer to another question of Mohar.

We also study the circular choice number of planar and outerplanar graphs with prescribed girth, and graphs with bounded density.