The crumby coloring conjecture for subcubic outerplanar graphs

The red-blue vertex partitions now known as crumby colorings originate in a conjecture of Thomassen related to Wegner's conjecture on squares of planar graphs.

In such a coloring, the blue vertices induce a graph of maximum degree at most one, while the red vertices induce a graph with no isolated vertices and no simple path with three edges.

Barát, Blázsik and Damásdi proved that every 2-connected outerplanar graph of maximum degree at most three admits a crumby coloring, and conjectured that the 2-connectivity assumption can be removed.

We prove this conjecture: every finite simple subcubic outerplanar graph admits a crumby coloring.

To prove the conjecture, we introduce a rooted grammar for subcubic outerplanar graphs.

The grammar describes such graphs recursively using rooted branches and two-terminal path fragments; cyclic blocks are handled by deleting the root to obtain a path fragment.

We correspondingly extend crumby colorings to crumby-admissible colorings: in a rooted branch the root, and in a path fragment the two terminals, are allowed to be temporary isolated red vertices.

This relaxation makes induction along the grammar possible while retaining only finite boundary information.

The induction reduces to verifying an explicit finite family of lower certificates, namely nonempty sets of boundary types and root states.

The required verification has two parts: the family must be closed under all steps of the decomposition, and every certified completed branch must contain a final-legal root state, so that the temporary defect disappears and the resulting coloring is a genuine crumby coloring.

This final step is computer-assisted: a stand-alone certificate checker, supplied with the paper, verifies the stated closure and crumby conditions for the supplied certificate.

All structural reductions and the certificate-induction principle are proved by hand.