Skip to Main content Skip to Navigation
New interface
Journal articles

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

Cited literature [25 references]  Display  Hide  Download
Contributor : Jean-Sébastien Sereni Connect in order to contact the contributor
Submitted on : Thursday, July 1, 2010 - 1:18:03 PM
Last modification on : Thursday, August 4, 2022 - 4:52:43 PM
Long-term archiving on: : Monday, October 22, 2012 - 5:11:42 PM


Files produced by the author(s)



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



Record views


Files downloads