6‐Star‐Coloring of Subcubic Graphs. Issue 2 (1st June 2012)

• Record Type: Journal Article
• Authors: Chen, Min; Raspaud, André; Wang, Weifan
• Is Part Of: Journal of graph theory. Volume 72:Issue 2(2013)
• Page Start: 128
• Page End: 145
• Publication Date: 2012-06-01
• Subjects: Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.21636
• Languages: English
• ISSNs: 0364-9024

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>A star coloring of an undirected graph <italic>G</italic> is a proper vertex coloring of <italic>G</italic> (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 <italic>G</italic> is the smallest integer <italic>k</italic> for which <italic>G</italic> admits a star coloring with <italic>k</italic> 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, and Reed (J Graph Theory 47(3) (2004), 140–153).</p> </abstract>