Discrete Mathematics & Theoretical Computer Science, Vol 13, No 3 (2011)

Font Size:  Small  Medium  Large

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

Min Chen, André Raspaud, Weifan Wang

Abstract


A proper vertex coloring of a graph G is 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)∈L(v). If G is L-star-colorable for any list assignment L with |L(v)|≥k for all v∈V(G), then G is called k-star-choosable. The star list chromatic number of G, denoted by χsl(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. Kündgen, C. Timmons, Star coloring planar graphs from small lists, J. Graph Theory, 63(4): 324-337, 2010].

Full Text: PDF PostScript