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.
Document type :
Journal articles
Liste complète des métadonnées

Cited literature [25 references]  Display  Hide  Download

https://hal.inria.fr/inria-00496432
Contributor : Jean-Sébastien Sereni <>
Submitted on : Thursday, July 1, 2010 - 1:18:03 PM
Last modification on : Friday, January 4, 2019 - 5:32:57 PM
Document(s) archivé(s) le : Monday, October 22, 2012 - 5:11:42 PM

File

HKMS09.pdf
Files produced by the author(s)

Identifiers

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⟩

Share

Metrics

Record views

483

Files downloads

145