The Smallest Subcubic Graph Without a Crumby Coloring

A red–blue coloring of the vertices of a graph is crumby if the blue vertices induce a subgraph of maximum degree at most one, while the red vertices induce a subgraph of minimum degree at least one containing no path on four vertices. Thomassen and Barát conjectured that such colorings exist for all 3-connected cubic, respectively all subcubic, graphs beyond the triangular prism; counterexamples were given by Bellitto, Klimošová, Merker, Witkowski and Yuditsky via a 48-vertex gadget, and by Pintér with K4-minor-free graphs on 18 and 40 vertices. Combining a compositional boundary-state calculus for graph fragments with an exhaustive, independently audited search, we determine the minimum order of a connected subcubic graph on at least seven vertices without a crumby coloring: it is 14, attained by exactly two graphs.