Skip to Main content Skip to Navigation

Circular Choosability

Frédéric Havet 1 Ross Kang 2 Tobias Müller 2 Jean-Sébastien Sereni 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : In this paper, we study the notion of circular choosability recently introduced by Mohar and Zhu. First, we provide a negative answer to a question of Zhu about circular cliques. We next prove that, for every graph G, cch(G) = O( ch(G) + ln |V(G)| ). We investigate a generalisation of circular choosability, circular f-choosability, when 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 6 <= tau <= 8, thereby providing a negative answer to another question of Mohar. Finally, we study the circular choice number of planar and outerplanar graphs with prescribed girth, and graphs with bounded density.
Document type :
Complete list of metadata
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, August 1, 2006 - 3:49:31 PM
Last modification on : Monday, October 12, 2020 - 10:30:26 AM
Long-term archiving on: : Monday, September 20, 2010 - 4:39:00 PM


  • HAL Id : inria-00086981, version 2


Frédéric Havet, Ross Kang, Tobias Müller, Jean-Sébastien Sereni. Circular Choosability. [Research Report] RR-5957, INRIA. 2007, pp.33. ⟨inria-00086981v2⟩



Record views


Files downloads