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

Abstract : 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].
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2011, Vol. 13 no. 3 (3), pp.97--110
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00990482
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 13 mai 2014 - 15:39:09
Dernière modification le : jeudi 11 janvier 2018 - 06:20:17
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:08:03

Fichier

1459-6706-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00990482, version 1

Collections

Citation

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, DMTCS, 2011, Vol. 13 no. 3 (3), pp.97--110. 〈hal-00990482〉

Partager

Métriques

Consultations de la notice

193

Téléchargements de fichiers

308