Disproving the Petersen Coloring Conjecture: Theoretical Analysis and an Infinite Family of Counterexamples
Abstract
In 1988, Jaeger conjectured that every bridgeless cubic graph G admits a Petersen coloring; that is, a map E(G) → E(P) mapping any two adjacent edges of G to two adjacent edges of the Petersen graph P. A positive resolution of Jaeger's conjecture would have immediately resolved several other famous and long-standing problems in graph theory. In July 2026, a 68-vertex counterexample was announced on X. Shortly afterwards, Putman independently presented two non-isomorphic 112-vertex counterexamples, relying solely on computer-assisted verification. In this paper, we present two counterexamples of order $52$, currently the smallest known, and provide a purely theoretical proof. In the second part, we construct an infinite family of cyclically $4$-edge-connected cubic graphs without a Petersen coloring for every even order at least $60$. Additionally, through computational verification, we show that any counterexample must have order at least $40$. Moreover, we show that our counterexamples provide a negative answer to other related problems. Finally, we conclude the paper by discussing key open problems and highlighting avenues for future work.
Related
- Counterexamples to Relaxed Multiplication in List Coloring
- A proof of Wang's planar D-coloring conjecture
- The Borowiecki-Broere Generalized Total Coloring Conjecture for Planar Graphs
- Counterexamples to the Monotone Completeness Conjecture
- Counterexamples to the ordinary Fried conjecture near hyperbolic metrics
BibTeX
@misc{goedgebeur2026disproving,
title = {{Disproving the Petersen Coloring Conjecture: Theoretical Analysis and an Infinite Family of Counterexamples}},
author = {Jan Goedgebeur and Jorik Jooken and Edita Máčajová and Davide Mattiolo and Giuseppe Mazzuoccolo and Nikolay Ulyanov},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.10028},
eprint = {2608.10028},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.10028},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Disproving the Petersen Coloring Conjecture: Theoretical Analysis and an Infinite Family of Counterexamples
AU - Jan Goedgebeur
AU - Jorik Jooken
AU - Edita Máčajová
AU - Davide Mattiolo
AU - Giuseppe Mazzuoccolo
AU - Nikolay Ulyanov
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2608.10028
UR - https://arxiv.org/abs/2608.10028
AB - In 1988, Jaeger conjectured that every bridgeless cubic graph G admits a Petersen coloring; that is, a map E(G) → E(P) mapping any two adjacent edges of G to two adjacent edges of the Petersen graph P. A positive resolution of Jaeger's conjecture would have immediately resolved several other famous and long-standing problems in graph theory. In July 2026, a 68-vertex counterexample was announced on X. Shortly afterwards, Putman independently presented two non-isomorphic 112-vertex counterexamples, relying solely on computer-assisted verification. In this paper, we present two counterexamples of order $52$, currently the smallest known, and provide a purely theoretical proof. In the second part, we construct an infinite family of cyclically $4$-edge-connected cubic graphs without a Petersen coloring for every even order at least $60$. Additionally, through computational verification, we show that any counterexample must have order at least $40$. Moreover, we show that our counterexamples provide a negative answer to other related problems. Finally, we conclude the paper by discussing key open problems and highlighting avenues for future work.
ER -