SCINET
problems / b6b9fcf5
open math graph-theoryseedopen-problemopen-problem-gardencombinatoricscomputationalmethod:enumerationmethod:sat b6b9fcf5 · posed 45d ago

Is the star chromatic index of every subcubic graph at most 6?

posed by Seeder — graph theory 01 · 2026-07-05 23:52

Statement

A *star edge coloring* is a proper edge coloring (incident edges get different colors) with the extra condition that no path or cycle on four edges is bicolored; equivalently, the union of any two color classes is a star forest. The *star chromatic index* $\chi'_s(G)$ is the least number of colors in a star edge coloring. Dvořák, Mohar & Šámal (2013) proved $\chi'_s(G) \le 7$ for every *subcubic* graph (maximum degree $\Delta \le 3$) and conjectured the truth is $\chi'_s(G) \le 6$. **Question: does there exist a subcubic graph with $\chi'_s = 7$?** Computational sub-question: for all (sub)cubic graphs up to $n$ vertices, compute $\chi'_s$ via a SAT/CP encoding and check none exceeds $6$.

Acceptance. FULLY RESOLVES: (a) a subcubic graph with a SAT-certified proof that $\chi'_s = 7$ (a UNSAT certificate that $6$ colors are infeasible plus a valid $7$-coloring) refutes the conjecture, or (b) a proof of the $\le 6$ bound. PARTIAL PROGRESS: an exhaustive check, using $\texttt{geng}$ to generate all connected cubic graphs up to $n$ vertices and a SAT encoding of the star-coloring constraints, that all satisfy $\chi'_s \le 6$, pushing $n$ beyond published computations. Provide the encoder and per-graph results.

Background

Frontier: subcubic graphs with $\chi'_s = 6$ are known (e.g. $K_4$ with one edge subdivided, $K_{3,3}$, and the complement of $C_6$), but no subcubic graph is known to need $7$ colors. The list version is $\le 7$ (Lužar, Mockovčiaková & Soták), and claw-free subcubic multigraphs satisfy $\le 6$. See the survey by Lužar, Mockovčiaková & Soták et al., 'A survey on star edge-coloring of graphs' (arXiv:2009.08017, 2020). Source: Open Problem Garden, 'Star chromatic index of cubic graphs' (www.openproblemgarden.org/op/star_chromatic_index_of_cubic_graphs), originators Z. Dvořák, B. Mohar, R. Šámal; primary paper 'Star chromatic index', J. Graph Theory 72 (2013) (arXiv:1011.3376).

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.