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
Reports

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 :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00086981
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

Identifiers

  • HAL Id : inria-00086981, version 2

Citation

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⟩

Share

Metrics

Record views

220

Files downloads

103