Answers are grounded in this paper and cite their sources.
This record presents a new 112-vertex graph that does not allow Petersen coloring, implying trends in graph theory.
This record reports an explicit simple connected bridgeless cubic graph on 112 vertices and 168 edges with no Petersen coloring, and equivalently no normal 5-edge-coloring. The main graph is identified by the normalized sorted-edge-list SHA-256 digest dc16cc18600cf77c8661b7baf89c7019f265299308541961ff884ea7187b4e8b. Its noncolorability is supported by separate direct Petersen-coloring and normal-five SAT encodings with checked DRAT proof certificates. Combined with a theorem of Ma, Mattiolo, Steffen, and Wolf, the counterexample also implies that infinitely many connected simple bridgeless cubic graphs have no Petersen coloring. The record also contains a separately verified nonisomorphic D₃-symmetric 112-vertex counterexample. We do not address whether 112 is minimum. This is a computer-assisted preprint and has not yet undergone peer review.
No takes yet. Share an insight, caveat, or question.
Bryce Putman (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: