Petersen coloring conjecture

High ★★★ Graph Theory » Coloring » Edge coloring

Author: Jaeger, Francois— posted by mdevos on 2007-03-07

Status partial high confidence

Jaeger's Petersen coloring conjecture (every bridgeless cubic graph admits a cycle-continuous mapping to the Petersen graph, equivalently a normal 5-edge-coloring) remains open. Significant partial results have been established: every bridgeless cubic graph admits a proper 5-edge-coloring in which at least $(4/5)|E(G)|$ edges are normal, and the conjecture has been verified for specific families such as snarks superpositioned by flower snarks. The problem has also been reformulated in terms of sublinear approximation bounds on abnormal edges.

Cited literature (5)

partial A remark on Petersen coloring conjecture of Jaeger (2012)

Vahan V. Mkrtchyan · arXiv preprint · arXiv:1201.4472

Introduces the Sylvester coloring conjecture as a stepping-stone and proves structural constraints: if a connected bridgeless cubic graph $G$ satisfies $G \prec P$ (Petersen) or $G \prec S$ (Sylvester), then $G$ equals that graph.
partial Partially normal 5-edge-colorings of cubic graphs (2019)

Ligang Jin, Yingli Kang · arXiv preprint · arXiv:1911.06759

Proves that every bridgeless cubic graph admits a proper 5-edge-coloring in which at least $|E(G)| - \mu_3(G) \geq (4/5)|E(G)|$ edges are normal, providing a quantitative approximation to the Petersen coloring conjecture.
partial Variations on the Petersen Colouring Conjecture (2020)

François Pirot, Jean-Sébastien Sereni, Riste Škrekovski · The Electronic Journal of Combinatorics · arXiv:1905.07913 · doi:10.37236/8515

Proves that every bridgeless cubic graph $G$ admits an edge-colouring with 4 colours such that at most $(4/5)|V(G)|$ edges fail the normality condition, and shows this bound is tight with the Petersen graph as the extremal example.
partial On sublinear approximations for the Petersen coloring conjecture (2021)

Davide Mattiolo, Giuseppe Mazzuoccolo, Vahan Mkrtchyan · arXiv preprint · arXiv:2104.09241

Reformulates the Petersen coloring conjecture as equivalent to the existence of a sublinear function bounding abnormal edges in normal 5-edge-colorings, providing a new quantitative perspective on the conjecture.
partial Normal 5-edge-coloring of some snarks superpositioned by Flower snarks (2023)

Jelena Sedlar, Riste Škrekovski · arXiv preprint · arXiv:2306.13340

Establishes sufficient conditions for the Petersen coloring conjecture to hold in snarks superpositioned by flower snarks, verifying the conjecture for this specific infinite family.

Reviewer notes. The conjecture remains fully open. The 4/5 normal-edge fraction appears in both Jin-Kang (2019) and Pirot-Sereni-Škrekovski (2020) with slightly different formulations (5-coloring vs. 4-coloring). The Mkrtchyan 2012 paper was published in Australasian Journal of Combinatorics 2013 but DOI was not confirmed. No counterexample or full proof was found in the literature searched. The ScienceDirect result for 'Normal 5-edge-coloring of some snarks superpositioned by the Petersen graph' was not fetched independently and is therefore not cited.

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

Conjecture. Let $ G $ be a cubic graph with no bridge . Then there is a coloring of the edges of $ G $ using the edges of the Petersen graph so that any three mutually adjacent edges of $ G $ map to three mutually adjancent edges in the Petersen graph.

Keywords: cubic · edge-coloring · Petersen graph

Discussion

This extrordainary conjecture asserts that in a very strong sense, every bridgeless cubic graph has all of the cycle-space properties posessed by the Petersen graph. If true, this conjecture would imply both The Berge-Fulkerson conjecture and The five cycle double cover conjecture . If $ G $ is a graph and $ C \subseteq E(G) $ we say that $ C $ is a binary cycle if every vertex in the graph $ (V(G),C) $ has even degree. If $ H $ is a graph and $ f : E(G) \rightarrow E(H) $ is a map, we say that $ f $ is cycle-continuous if the pre-image of every binary cycle is a binary cycle. The following conjecture is an equivalent reformulation of the Petersen coloring conjecture. Conjecture (Petersen coloring conjecture (2)) Every bridgeless graph has a cycle-continuous mapping to the Petersen graph.