|Résumé||A star coloring of an undirected graph G is a proper vertex coloring of G (i.e., no two adjacent vertices are assigned the same color) such that no path on four vertices is 2-colored. The star chromatic number of G is the smallest integer k for which G admits a star coloring with k colors.
In this paper, we prove that every subcubic graph is 6-star-colorable. Moreover, the upper bound 6 is best possible, based on the example constructed by Fertin, Raspaud, Reed in [G. Fertin, A. Raspaud, B. Reed, Star coloring of graphs. J. Graph Theory, 47(3): 140-153, 2004.] |