Star chromatic index of cubic graphs

Medium ★★ Graph Theory

Authors: Dvorak, Zdenek, Mohar, Bojan, Samal, Robert— posted by Robert Samal on 2010-11-16

Status partial high confidence

The conjecture that every (sub)cubic graph $G$ satisfies $\chi_s'(G) \le 6$ remains open. Significant partial progress has been made: the bound $\chi_s'(G) \le 6$ has been confirmed for subcubic multigraphs with $\text{mad}(G) < 5/2$, for cubic Halin graphs, and an infinite family of cubic graphs achieving $\chi_s'(G) = 6$ has been constructed (confirming tightness), but the full conjecture is unresolved.

Cited literature (3)

partial Star chromatic index of subcubic multigraphs (2017)

Hui Lei, Yongtang Shi, Zi-Xia Song · arXiv preprint · arXiv:1701.04105

Proves $\chi_s'(G) \le 6$ for every subcubic multigraph $G$ with $\text{mad}(G) < 5/2$, and $\chi_s'(G) \le 5$ if $\text{mad}(G) < 24/11$.
partial On star edge colorings of bipartite and subcubic graphs (2021)

Carl Johan Casselgren, Jonas B. Granholm, André Raspaud · Discrete Applied Mathematics · arXiv:1912.02467

Settles the conjecture $\chi_s'(G) \le 6$ for cubic Halin graphs, and proves tight bounds for star chromatic index of complete bipartite and restricted bipartite graphs.
partial Star Edge Coloring of Outerplanar and Cubic Graphs: Bounds and Constructions (2025)

Xingchao Deng, Yan Liu, Xinge Feng · Bulletin of the Malaysian Mathematical Sciences Society · doi:10.1007/s40840-025-01875-9

Constructs an infinite sequence of cubic graphs $G$ with $\chi_s'(G) = ch_s'(G) = 6$, confirming the tightness of the conjectured bound, and establishes new bounds for striped maximal outerplanar graphs.

Reviewer notes. The Lei-Shi-Song 2017 paper (arXiv 1701.04105) may have been published in a journal; DOI not verified from the fetch. The Casselgren-Granholm-Raspaud paper was verified via its arXiv preprint (1912.02467); the ScienceDirect page returned 403. The Springer 2025 paper was verified via a redirect URL with a temporary session code; the canonical DOI is 10.1007/s40840-025-01875-9. No paper resolving the full conjecture for all subcubic graphs was found.

Auto-reviewed 2026-05-08 with claude-sonnet-4-6 (worker 05) (web search enabled).

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

Keywords: edge coloring · star coloring

Discussion

The star chromatic number is the more usual concept [ACKKR,FRR]. Star chromatic index of a graph $ G $ is simply the star chromatic number of the line graph $ L(G) $ ; the definition given above is easily seen to be equivalent. Dvořák, Mohar, and Šámal [DMS] show that every (sub)cubic graph $ G $ , satisfies $ \chi_s'(G) \le 7 $ ? On the other hand, it is simple to check that $ \chi_s'(K_{3,3])=6 $ , 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 . doi:10.1002/jgt.20029
★ [DMS] Dvořák, Zdeněk; Mohar, Bojan; Šámal, Robert: Star chromatic index, arXiv:1011.3376 . arXiv:1011.3376