The Petersen Coloring Conjecture, posed by Jaeger in 1988, proposes that any bridgeless cubic graph (a network where every node connects to exactly three edges and no single edge is a bridge holding the graph together) can be "colored" using the edges of the famous Petersen graph as a kind of template. This conjecture is important because it would imply several other major open problems in graph theory. Researchers have long suspected it might be false, but no concrete counterexample had been found. A related concept, called a normal 5-edge-coloring, is equivalent to having a Petersen coloring, so disproving one disproves the other.
The authors construct an explicit graph with 112 vertices that has no valid Petersen coloring. The graph is built carefully from smaller modular pieces, somewhat like assembling a structure from standardized components. To prove that no valid coloring exists, they translated the problem into a format called SAT, which is a standard computational logic problem that solvers can check automatically. A modern SAT solver confirmed the graph has no solution, and the proof was independently verified using a separate checking tool, giving strong confidence in the result. The paper also provides all the technical files, hashes, and verification programs publicly so others can check the work independently.
The consequences extend well beyond a single example. By combining this finding with a previously known theorem, the authors show that infinitely many bridgeless cubic graphs must also lack a Petersen coloring, making this a significant disproof of the conjecture rather than just an isolated curiosity. They also found a second, structurally distinct 112-vertex counterexample with extra symmetry, verified separately. The authors leave open whether 112 is the smallest possible counterexample, meaning a smaller one might still exist but has not yet been found.