6‐Star‐Coloring of Subcubic Graphs |
| |
Authors: | Min Chen André Raspaud Weifan Wang |
| |
Institution: | 1. DEPARTMENT OF MATHEMATICS, ZHEJIANG NORMAL UNIVERSITY, , JINHUA 321004, CHINA;2. LaBRI UMR CNRS 5800, UNIVERSITE BORDEAUX I, , 33405 TALENCE CEDEX, FRANCE |
| |
Abstract: | 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, and Reed (J Graph Theory 47(3) (2004), 140–153). |
| |
Keywords: | subcubic graph vertex coloring proper coloring star‐coloring |
|
|