A 112-Vertex Counterexample to the Petersen Coloring Conjecture

Abstract

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.