Circular Choosability - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2007

Circular Choosability

Résumé

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.
Fichier principal
Vignette du fichier
RR-5957.pdf (414.25 Ko) Télécharger le fichier

Dates et versions

inria-00086981 , version 1 (20-07-2006)
inria-00086981 , version 2 (01-08-2006)

Identifiants

  • HAL Id : inria-00086981 , version 2

Citer

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⟩
230 Consultations
107 Téléchargements

Partager

Gmail Facebook X LinkedIn More