The Petersen coloring conjecture (Jaeger 1985) asserts that every bridgeless graph that is cubic admits a Petersen coloring. Such a coloring is a map from its edges to the edges of the Petersen graph that sends the three edges incident with each graph vertex to the three edges incident with some graph vertex of the Petersen graph. The name refers to the use of the edges of the Petersen graph as colors, with their incidence pattern preserved at each graph vertex.
Putman (2026) announced two nonisomorphic 112-vertex counterexamples. The absence of Petersen colorings is certified by independently checkable unsatisfiability certificates for explicit Boolean functions. The accompanying archive supplies the graphs, encodings, certificates, and verification programs. NeuralReformist (2026) announced an earlier 68-vertex counterexample, crediting GPT-5.6 Sol Ultra. The announcement supplies an encoded graph. Neither announcement determines the minimum possible vertex count.
The conjecture would imply the Fulkerson conjecture and a strengthening of the cycle double cover conjecture. A counterexample to Petersen coloring does not by itself refute either of these weaker assertions.
