Star chromatic index of cubic graphs

Star chromatic index of cubic graphs

Definitions and mathematical statement

Let $G=(V,E)$ be a finite simple undirected graph. Its maximum degree $\Delta(G)$ is the largest number of edges incident with a vertex. It is subcubic if $\Delta(G)\le3$, and cubic if every vertex has degree three. An edge colouring $\varphi:E\to\{1,\ldots,q\}$ is proper when edges with a common endpoint have different colours.

Such a colouring is a star edge colouring if no path of four edges and no cycle of four edges uses only two colours. A path here has five distinct vertices; it need not be an induced path. In a proper colouring, a forbidden two-coloured four-edge path or cycle necessarily alternates between its two colours. Equivalently, the subgraph consisting of any two colour classes has components that are paths of at most three edges, together with isolated vertices.

The star chromatic index $\chi'_s(G)$ is the least number of colours in a star edge colouring. The conjecture is \[ \chi'_s(G)\le6\qquad\text{for every finite subcubic graph }G. \] The bound is independent of the number of vertices and of whether $G$ is connected, planar or bipartite. There is no preassigned colouring or list of allowed colours at individual edges.

The restriction concerns paths with four edges, not four vertices, and applies even when extra edges join vertices of the path. Ordinary proper edge colouring alone does not impose it. A resolution must either give the six-colour guarantee for every such graph or exhibit a subcubic graph for which every proper six-colouring has a forbidden configuration.

Short English statement

Can every graph of maximum degree at most three be edge-coloured with six colours while avoiding every two-coloured four-edge path or cycle?

Research attempt

Scope and process.

GPT-6 Astra Ultra, 1 October 2026. This attempt keeps the catalogue statement above, checks primary literature, and develops a restricted argument with an adversarial gap audit. The proofs below are the mathematical output of this attempt, not a claim of novelty or external certification.

Literature and attack plan.

Dvořák, Mohar and Šámal [R1] establish a seven-colour bound for subcubic graphs and formulate the six-colour problem. Lei, Shi and Song [R2] prove six-colour results under a maximum-average-degree restriction. The elementary construction below covers all subcubic forests directly. It is weaker than those results and is presented to isolate precisely the cycle obstruction to one natural depth-colouring approach.

Rooting and the six colours.

Consider a tree $T$ of maximum degree at most three. A one-vertex component has no edges to colour. Otherwise choose a leaf as root. Every vertex then has at most two children, including the root, which has just one. Let $h(v)$ denote distance from the root. Use three disjoint pairs of colours \[ C_0=\{1,2\},\quad C_1=\{3,4\},\quad C_2=\{5,6\}. \] An edge from a parent to a child of depth $h$ receives a colour in $C_{h\bmod3}$. At each parent assign distinct colours to its at most two child edges; choices at different parents are independent. This completely specifies a valid construction with six available colours.

Proof of properness.

At a nonroot vertex of depth $h$, its parent edge has a colour in $C_{h\bmod3}$, while its child edges have colours in $C_{(h+1)\bmod3}$. These pairs are disjoint. Distinct child edges receive distinct colours by construction. At the root there is only one edge. Thus every pair of incident edges differs in colour.

Proof of the star condition.

Take any simple four-edge path in $T$. Its unique vertex of minimum depth separates it into branches of lengths $a,b\ge0$ with $a+b=4$. If $\max(a,b)\ge3$, that branch contains three consecutive edge depths. Their residues modulo three are distinct, so these three edges alone use three different palette pairs and therefore three colours.

The only remaining case is $a=b=2$. The two edges immediately incident with the minimum-depth vertex are distinct child edges, at the same depth, so they use the two different colours of one pair. Each outer edge has the next depth and a colour in a disjoint pair. Again the path has at least three colours. A tree has no four-cycle at all. Hence the colouring is a star edge colouring, proving \[ \chi'_s(T)\le6\quad\text{for every subcubic tree }T. \tag{1} \] Colour each component of a forest independently using the same palette. A path or cycle cannot cross components, so $1$ extends to all subcubic forests.

A checked failure of a smaller periodic scheme.

One might use just two depth palettes, assigning two colours per parity, and hope that properness rules out a bichromatic four-edge path. On a path rooted at an endpoint, however, nothing prevents its four consecutive edge colours from being $1,3,1,3$. Properness holds, while the star condition fails. The third depth residue in the construction is doing real work; the proof cannot simply be compressed from six to four colours by deleting one palette.

Rooting a spanning tree of a cubic graph also does not immediately extend $1$. A non-tree edge may connect vertices with unrelated depths. Giving it any of the six colours must simultaneously respect incident edges and every four-edge path through it. The depth monotonicity argument applies only to paths in the tree, and offers no control of these new configurations. This is the first failed extension, not a proof that a particular cubic graph requires seven colours.

Verification.

The standard-library script scripts/check_attempt_batch_graphs_2026_10_01.py decoded every Prüfer word of orders two through six, retained all 1,310 labelled subcubic trees, applied this construction, and checked properness and all 3,720 oriented four-edge paths in those trees. All checks passed. This finite test is independent support for the stated universal forest proof.

The minimum-depth decomposition used above is valid for tree paths even when their endpoints have unequal depths. All unordered splits of four were covered: $(0,4)$, $(1,3)$ and $(2,2)$. Rooting at a leaf is essential for the two-child assignment; an arbitrary degree-three root would require three colours in one pair. Isolates and single edges were handled separately. No assumption of inducedness entered: every simple path in a tree is already induced, and the target forbids all simple four-edge paths.

Final status and gap.

We have an explicit six-colour algorithm and proof for the forest subclass. Handling cycles and their interactions while retaining only six colours remains unproved. The full subcubic conjecture is UNRESOLVED by this attempt; the forest construction is not claimed as new progress beyond the cited literature.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3115 (OPG-37271), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Star chromatic index of cubic graphs. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/star_chromatic_index_of_cubic_graphs.
• R1 Z. Dvořák, B. Mohar and R. Šámal, Star chromatic index, arXiv:1011.3376; Journal of Graph Theory 72 $2013$, 313--326. Primary abstract checked. https://arxiv.org/abs/1011.3376.
• R2 H. Lei, Y. Shi and Z.-X. Song, Star chromatic index of subcubic multigraphs, arXiv:1701.04105. Primary abstract checked for the bound under $\operatorname{mad}(G)<5/2$. https://arxiv.org/abs/1701.04105.