
Star chromatic index of cubic graphs
The star chromatic index of a graph
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.


The star chromatic number is the more usual concept [ACKKR,FRR]. Star chromatic index of a graph is simply the star chromatic number of the line graph
; the definition given above is easily seen to be equivalent.
Dvořák, Mohar, and Šámal [DMS] show that every (sub)cubic graph , satisfies
? On the other hand, it is simple to check that
, so the conjecture, if true, is tight.
Bibliography
[ACKKR] Albertson, Michael O.; Chappell, Glenn G.; Kierstead, Hal A.; Kündgen, André; Ramamurthi, Radhika: Coloring with no 2-Colored P4's, The Electronic Journal of Combinatorics 11 (1).
[FRR] Fertin, Guillaume; Raspaud, André; Reed, Bruce, Star coloring of graphs, Journal of Graph Theory 47 (3): 163-182, doi:10.1002/jgt.20029 .
*[DMS] Dvořák, Zdeněk; Mohar, Bojan; Šámal, Robert: Star chromatic index, arXiv:1011.3376.
* indicates original appearance(s) of problem.