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 , 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.
Type de document :
Rapport
[Research Report] RR-5957, INRIA. 2007, pp.33
Liste complète des métadonnées

https://hal.inria.fr/inria-00086981
Contributeur : Rapport de Recherche Inria <>
Soumis le : mardi 1 août 2006 - 15:49:31
Dernière modification le : jeudi 11 janvier 2018 - 16:04:51
Document(s) archivé(s) le : lundi 20 septembre 2010 - 16:39:00

Fichiers

Identifiants

  • HAL Id : inria-00086981, version 2

Collections

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〉

Partager

Métriques

Consultations de la notice

282

Téléchargements de fichiers

101