Circular choosability

Abstract : We study circular choosability, a notion recently introduced by Mohar and by 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 generalisation 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.
Type de document :
Article dans une revue
Journal of Graph Theory, Wiley, 2009, 61 (4), pp.241--270. <10.1002/jgt.20375>
Liste complète des métadonnées

https://hal.inria.fr/inria-00496432
Contributeur : Jean-Sébastien Sereni <>
Soumis le : jeudi 1 juillet 2010 - 13:18:03
Dernière modification le : mercredi 12 octobre 2016 - 01:23:21
Document(s) archivé(s) le : lundi 22 octobre 2012 - 17:11:42

Fichier

HKMS09.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Frédéric Havet, Ross Kang, Tobias Müller, Jean-Sébastien Sereni. Circular choosability. Journal of Graph Theory, Wiley, 2009, 61 (4), pp.241--270. <10.1002/jgt.20375>. <inria-00496432>

Partager

Métriques

Consultations de
la notice

334

Téléchargements du document

107