3-Edge-Coloring Conjecture

High ★★★ Graph Theory accessible to undergrads

Authors: Arthur, Hoffmann-Ostenhof— posted by arthur on 2020-04-28

Status partial medium confidence

The conjecture—that every connected cubic graph admitting a $3$-edge coloring (equivalently, a nowhere-zero $4$-flow) contains an edge $e$ whose suppression to a cubic graph preserves the $3$-edge coloring—remains open in general. Mattiolo (2025) proved the equivalent $4$-removable-edge formulation for all bipartite cubic graphs and derived an approximation result for the non-bipartite case, but the full conjecture is unresolved.

Cited literature (1)

partial On removable edge subsets in graphs with a nowhere-zero $4$-flow (2025)

Davide Mattiolo · arXiv preprint · arXiv:2511.01556

Proves the Hoffmann-Ostenhof conjecture (every cubic graph with a nowhere-zero 4-flow has a 4-removable edge) for bipartite cubic graphs, and establishes an approximation result for non-bipartite cubic graphs; the full conjecture remains open.

Reviewer notes. Most search hits about 'Hoffmann-Ostenhof conjecture for traceable/claw-free cubic graphs' concern the distinct 3-Decomposition Conjecture (spanning tree + matching + 2-regular subgraph), not the 3-Edge-Coloring Conjecture under review; those papers (arXiv:1607.04768, 1810.00074) predate the 2020-04-28 posting and concern a different problem, so they are excluded. The OPG page was unreachable (ECONNREFUSED) during this review. The Mattiolo 2025 paper is the only post-posting work found that directly addresses the stated conjecture; other 2024-2025 papers on 3-edge-coloring of toroidal/projective-planar cubic graphs address different questions.

Auto-reviewed 2026-05-07 with claude-sonnet-4-6 (web search enabled) · 1117s.

Conjecture. Suppose $ G $ with $ |V(G)|>2 $ is a connected cubic graph admitting a $ 3 $ -edge coloring. Then there is an edge $ e \in E(G) $ such that the cubic graph homeomorphic to $ G-e $ has a $ 3 $ -edge coloring.

Keywords: 3-edge coloring · 4-flow · removable edge

Discussion

Reformulation via 4-flows: Conjecture Suppose $ G $ is a cubic graph with a nowhere-zero $ 4 $ -flow, then there is an edge $ e \in E(G) $ such that $ G-e $ has a nowhere-zero $ 4 $ -flow.