HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 Connect in order to contact the contributor
Submitted on : Tuesday, August 1, 2006 - 3:49:31 PM
Last modification on : Friday, February 4, 2022 - 3:11:41 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