Disproving the Petersen Coloring Conjecture: Theoretical Analysis and an Infinite Family of Counterexamples

Jan Goedgebeur; Jorik Jooken; Edita Máčajová; Davide Mattiolo; Giuseppe Mazzuoccolo; Nikolay Ulyanov

Disproving the Petersen Coloring Conjecture: Theoretical Analysis and an Infinite Family of Counterexamples

Jan Goedgebeur, Jorik Jooken, Edita Máčajová, Davide Mattiolo, Giuseppe Mazzuoccolo, Nikolay Ulyanov

arXivarxiv/2608.10028Aug 9, 2026math.COscore 0

In 1988, Jaeger conjectured that every bridgeless cubic graph $G$ admits a Petersen coloring; that is, a map $E(G) \to 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…

Source JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2608.10028
curl -X POST /api/v1/records/arxiv/2608.10028/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.10028/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'