Premium
6‐Star‐Coloring of Subcubic Graphs
Author(s) -
Chen Min,
Raspaud André,
Wang Weifan
Publication year - 2013
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21636
Subject(s) - combinatorics , mathematics , fractional coloring , complete coloring , edge coloring , list coloring , star (game theory) , vertex (graph theory) , brooks' theorem , graph , discrete mathematics , chromatic scale , graph power , line graph , mathematical analysis
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).