3-Edge-Coloring Conjecture

Definitions and mathematical statement

Let $G$ be a finite connected cubic graph with more than two vertices. Here cubic means that every vertex has degree three, and the starting graph is simple. A proper three-edge-coloring assigns one of three colors to each edge so that edges sharing a vertex receive distinct colors; consequently every vertex sees all three colors.

For an edge $e=uv$, delete $e$. The vertices $u$ and $v$ now have degree two. Suppress each of them: replace the two remaining incident edges through that vertex by one edge joining their other ends. Denote the resulting cubic multigraph by $G\mathbin{\ominus}e$. Parallel edges created by suppression are retained as distinct edges. A loop, if created in a more general multigraph version, cannot receive a proper edge color. The question asks whether every three-edge-colorable $G$ has at least one edge $e$ for which $G\mathbin{\ominus}e$ is again three-edge-colorable.

Equivalently, the deleted graph $G-e$ should admit a nowhere-zero flow over $\mathbb Z_2\times\mathbb Z_2$: assign a nonzero group element to every remaining edge so that the sum of incident values at each vertex is zero. At a degree-two vertex the two values must agree, making suppression legitimate; at a degree-three vertex the three nonzero values must all differ. The coloring after deletion and suppression is allowed to be entirely different from any initially supplied coloring of $G$.

Short English statement

Does every connected three-edge-colorable cubic graph have an edge whose deletion and suppression leaves another three-edge-colorable cubic multigraph?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3141 (OPG-60046), OpenGarden. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, 3-Edge-Coloring Conjecture. Original problem and discussion. http://www.openproblemgarden.org/op/3_edge_coloring_conjecture.