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