6‐Star‐Coloring of Subcubic Graphs
Min Chen, André Raspaud, Weifan Wang · Journal of Graph Theory · 2012
Abstract A star coloring of an undirected graphGis a proper vertex coloring ofG(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 ofGis the smallest integerkfor whichGadmits a star coloring withkcolors. 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, and Reed (J Graph Theory 47(3) (2004), 140–153).