z-logo
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).

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here