Published 2009 | Version v1
Journal article

Circular choosability

Contributors

Others:

Description

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.

Abstract

International audience

Additional details

Identifiers

URL
https://hal.inria.fr/inria-00496432
URN
urn:oai:HAL:inria-00496432v1