8-star-choosability of a graph with maximum average degree less than 3 - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics and Theoretical Computer Science Année : 2011

8-star-choosability of a graph with maximum average degree less than 3

Résumé

A proper vertex coloring of a graphGis called a star-coloring if there is no path on four vertices assigned to two colors. The graph G is L-star-colorable if for a given list assignment L there is a star-coloring c such that c(v) epsilon L(v). If G is L-star-colorable for any list assignment L with vertical bar L(v)vertical bar \textgreater= k for all v epsilon V(G), then G is called k-star-choosable. The star list chromatic number of G, denoted by X-s(l)(G), is the smallest integer k such that G is k-star-choosable. In this article, we prove that every graph G with maximum average degree less than 3 is 8-star-choosable. This extends a result that planar graphs of girth at least 6 are 8-star-choosable [A. Kundgen, C. Timmons, Star coloring planar graphs from small lists, J. Graph Theory, 63(4): 324-337, 2010].
Fichier principal
Vignette du fichier
1459-6706-1-PB.pdf (515.66 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00990482 , version 1 (13-05-2014)

Identifiants

Citer

Min Chen, André Raspaud, Weifan Wang. 8-star-choosability of a graph with maximum average degree less than 3. Discrete Mathematics and Theoretical Computer Science, 2011, Vol. 13 no. 3 (3), pp.97--110. ⟨10.46298/dmtcs.561⟩. ⟨hal-00990482⟩

Collections

CNRS TDS-MACS
153 Consultations
815 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More