{"id":"arxiv/2608.10012","url":"https://arxiv.org/abs/2608.10012","tags":["math.CO"],"score":0,"title":"A 112-Vertex Counterexample to the Petersen Coloring Conjecture","domain":"math.CO","source":"arxiv","authors":["Bryce Putman"],"reviews":0,"subject":"math.CO","summary":"We give an explicit simple bridgeless cubic graph on 112 vertices with no Petersen coloring, and hence no normal 5-edge-coloring. The graph is identified by the SHA-256 digest in Theorem 1.1. It is assembled from three copies of a four-pole L and a claw six-pole C; in turn, L is assembled from four copies of a four-pole F and one copy of C, where F is obtained from the Petersen graph by deleting the endpoints of one edge. We give direct SAT formulations for Petersen colorings and normal 5-edge-colorings. CaDiCaL 3.0.1 returned UNSAT for both formulas, and drat-trim verified the resulting…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-08","reactions":{}}