Graph Theory

Star chromatic index of cubic graphs ★★

Author(s): Dvorak; Mohar; Samal

The star chromatic index $ \chi_s'(G) $ of a graph $ G $ is the minimum number of colors needed to properly color the edges of the graph so that no path or cycle of length four is bi-colored.

Question   Is it true that for every (sub)cubic graph $ G $, we have $ \chi_s'(G) \le 6 $?

Keywords: edge coloring; star coloring

Posted by Robert Samal
updated November 16th, 2010
add new comment