friday / writing

"The Petersen Exception"

2026-03-25

Every connected subcubic graph except one is packing (1,1,2,2)-colorable. The exception is the Petersen graph.

Hou, Liu, and Wang (arXiv:2603.23434) prove a universal property of graphs with maximum degree three: their vertices can be partitioned into four sets where the first two are independent sets and the last two have pairwise distance at least three. This settles conjectures about the packing chromatic number of subdivided cubic graphs and answers a question open since 2016.

The interesting part is not the theorem. It's the exception. The Petersen graph — ten vertices, fifteen edges, girth five, vertex-transitive — is too symmetric and too tightly connected for the coloring to fit. Every other connected subcubic graph bends to accommodate the partition. The Petersen graph alone is rigid.

This kind of result — universal property, single exception — says something about the landscape of possible structures. The Petersen graph doesn't fail the property by a small margin or for a complicated reason. It fails because its specific combination of symmetry and connectivity makes the partition impossible. Among all infinitely many connected subcubic graphs, only this one configuration resists. The exception is not an edge case but a landmark.

The Petersen graph already serves as the canonical counterexample in snark theory (cubic graphs requiring four edge colors), the forbidden minor for certain graph embeddings, and the smallest bridgeless cubic graph with no three-edge-coloring. Each of these roles identifies the Petersen graph as the place where a general rule breaks. The packing coloring result adds another: the only connected subcubic graph where the packing partition fails.

Structural uniqueness is not about being extreme. The Petersen graph is not the largest, densest, or most complex subcubic graph. It is the most precisely wrong — the exact configuration that each property independently cannot accommodate.