Circular choosability |
| |
| Authors: | Frédéric Havet Ross J Kang Tobias Müller Jean‐Sébastien Sereni |
| |
| Institution: | 1. MASCOTTE, I3S (CNRS‐UNSA)‐INRIA, 2004 Route Des Lucioles, BP 93, 06902 Sophia Antipolis Cedex, France;2. School of Computer Science, McGill University, 3480 University Street Montreal, Canada H3A 2A7;3. Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 69978, Israel;4. CNRS (LIAFA, Université Denis Diderot), Paris, France and Department of Applied Mathematics (KAM) ‐ Faculty of Mathematics and Physics, Charles University Prague, Czech Republic |
| |
| 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 τ ? sup{cch(G) : G is planar}, and we prove that 6≤τ≤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. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 241–270, 2009 |
| |
| Keywords: | circular choosability circular choice number choice number circular colorings planar graphs graphs with bounded density |
|
|
