The Petersen coloring conjecture (Jaeger 1988) asserts that every bridgeless graph that is cubic admits a Petersen coloring.
NeuralReformist (2026) announced a 68-vertex counterexample, crediting GPT-5.6 Sol Ultra. The announcement supplies an encoded graph. Putman (2026) subsequently announced two nonisomorphic 112-vertex counterexamples. For these two graphs, the absence of Petersen colorings is certified by independently checkable unsatisfiability certificates for explicit Boolean functions. Putman's accompanying archive supplies the graphs, encodings, certificates, and verification programs. Neither NeuralReformist's nor Putman's announcement determines the minimum possible vertex count.
Goedgebeur et al. (2026) gave a theoretical proof for two 52-vertex counterexamples, the smallest
known, and constructed an infinite family of cubic graphs
of girth 5 with cyclic
edge connectivity at least 4 without Petersen
colorings for every even vertex
count at least 60. The 60-vertex and 68-vertex members of this family are subgraphs of the Hamming graph 
,
the graph Cartesian product of four copies
of the complete graph 
. Their exhaustive computations exclude counterexamples
with fewer than 40 vertices. Thus the minimum possible
vertex count lies between 40 and 52 inclusive. Whether
a counterexample with cyclic
edge connectivity at least 5 exists remains open.
The conjecture would imply the Fulkerson conjecture and a strengthening of the cycle double cover conjecture, though a counterexample to Petersen coloring would not by itself refute either of these weaker assertions. Goedgebeur et al. (2026) computationally verified that the two 52-vertex, one 68-vertex, and two 112-vertex counterexamples have perfect matching cover index at most 4 and admit a cycle double cover consisting of five even subgraphs, so none refutes either assertion.
Small counterexample graphs on 
vertices will be implemented in a future version of
the Wolfram Language as GraphData[
"PetersenColoringCounterexample",
n,
k
],
where 
indexes the counterexamples with 
vertices.
