Min Chen ; André Raspaud ; Weifan Wang - 8-star-choosability of a graph with maximum average degree less than 3

dmtcs:561 - Discrete Mathematics & Theoretical Computer Science, December 31, 2011, Vol. 13 no. 3 - https://doi.org/10.46298/dmtcs.561
8-star-choosability of a graph with maximum average degree less than 3Article

Authors: Min Chen 1; André Raspaud 2; Weifan Wang 1

  • 1 Department of Mathematics [Jinhua]
  • 2 Laboratoire Bordelais de Recherche en Informatique

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].

Volume: Vol. 13 no. 3
Section: Graph and Algorithms
Published on: December 31, 2011
Accepted on: June 9, 2015
Submitted on: November 4, 2009
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

1 Document citing this article

Consultation statistics

This page has been seen 759 times.
This article's PDF has been downloaded 360 times.