pith. sign in

arxiv: 2605.04706 · v1 · submitted 2026-05-06 · 🧮 math.CO

Subcubic K₄-minor-free graphs without crumby colorings

J\'ozsef Pint\'er This is my paper

Pith reviewed 2026-05-08 16:39 UTC · model grok-4.3

classification 🧮 math.CO
keywords crumby coloringsK4-minor-free graphssubcubic graphspartial 2-treesvertex coloringsgraph minorsconjectures on colorings
0
0 comments X

The pith

K4-minor-free subcubic graphs on 18 vertices exist without crumby colorings.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper disproves the conjecture that every K4-minor-free graph admits a crumby coloring. It does so by exhibiting an explicit connected subcubic partial 2-tree on 18 vertices that has no such coloring. A second counterexample that is 2-connected has 40 vertices. This shows that the failure of crumby colorability occurs already among graphs of treewidth two.

Core claim

We construct a connected subcubic partial 2-tree on 18 vertices that admits no crumby coloring, thereby disproving the conjecture that every K4-minor-free graph admits one. We also construct a 2-connected subcubic partial 2-tree on 40 vertices with the same property. Consequently, the obstruction to crumby colorability already occurs within treewidth two, even under 2-connectivity.

What carries the argument

The explicit counterexample graphs: a connected subcubic partial 2-tree on 18 vertices and a 2-connected subcubic partial 2-tree on 40 vertices, each verified by exhaustive enumeration to admit no red-blue coloring in which blue vertices have maximum degree at most 1, red vertices have minimum degree at least 1, and the red subgraph contains no P4.

If this is right

  • The conjecture that every K4-minor-free graph admits a crumby coloring is false.
  • Crumby colorability fails for some graphs of treewidth two.
  • 2-connectivity does not guarantee a crumby coloring for subcubic K4-minor-free graphs.
  • The obstruction to crumby colorings appears in the class of partial 2-trees.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • These small counterexamples suggest that any algorithm deciding the existence of crumby colorings must handle treewidth-two graphs with care.
  • Characterizing exactly which K4-minor-free graphs admit crumby colorings is now a natural follow-up question.
  • The disproof indicates that stronger connectivity or planarity conditions may be needed for positive results on crumby colorings.
  • Similar explicit constructions could be used to test the limits of related coloring conjectures in minor-closed families.

Load-bearing premise

The two constructed graphs are K4-minor-free and subcubic, and exhaustive verification confirms they have no crumby coloring.

What would settle it

Discovery of a red-blue vertex coloring on the 18-vertex graph in which the blue vertices induce a matching, the red vertices induce a graph with minimum degree at least 1, and no red path on four vertices would show that this graph admits a crumby coloring.

Figures

Figures reproduced from arXiv: 2605.04706 by J\'ozsef Pint\'er.

Figure 1
Figure 1. Figure 1: The connected counterexample G18, drawn as two copies of the rooted graph F joined by the edge x1x2. Barát, Blázsik and Damásdi subsequently studied which restricted subcubic graph classes still admit crumby colorings [2]. They proved positive results for 2-connected outerplanar graphs, sub￾divisions of K4, 1-subdivisions of cubic graphs, and genuine subdivisions of subcubic graphs. Since the prototype cou… view at source ↗
Figure 2
Figure 2. Figure 2: The 2-connected counterexample G40. Small labels mark the roles x, a, b, c, d, e, f, g, h inside the four copies of F. Then add the following ears, in the displayed order: 0 − 2 − 3 − 1, 2 − 4 − 6 − 5 − 3, 5 − 7 − 9 − 8 − 6, 7 − 10 − 8, 11 − 13 − 14 − 12, 13 − 15 − 17 − 16 − 14, 16 − 18 − 20 − 19 − 17, 18 − 21 − 19, 30 − 23 − 25 − 24 − 22, 24 − 26 − 28 − 27 − 25, 26 − 29 − 27, 31 − 32 − 34 − 33 − 39, 33 − … view at source ↗
read the original abstract

Motivated by Wegner's conjecture on squares of planar graphs, Thomassen conjectured that every 3-connected cubic graph on at least eight vertices admits a red-blue vertex coloring in which the blue subgraph has maximum degree at most 1, while the red subgraph has minimum degree at least 1 and contains no $P_4$. Such colorings are now called crumby colorings. Although this conjecture was disproved in general by Bellitto, Klimo\v{s}ov\'a, Merker, Witkowski and Yuditsky, positive results of Bar\'at, Bl\'azsik and Dam\'asdi led them, in the same subcubic setting, to conjecture that every $K_4$-minor-free graph admits a crumby coloring. We disprove this conjecture with a connected subcubic partial 2-tree on 18 vertices. We also disprove its natural 2-connected version with a 2-connected subcubic partial 2-tree on 40 vertices with no crumby coloring. Consequently, the obstruction to crumby colorability already occurs within treewidth two, even under 2-connectivity.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The paper disproves the conjecture (due to Barát, Blázsik and Damásdi) that every K4-minor-free graph admits a crumby coloring by exhibiting two explicit counterexamples in the class of subcubic partial 2-trees: a connected 18-vertex graph and a 2-connected 40-vertex graph, neither of which admits a red-blue vertex partition in which the blue induced subgraph has maximum degree at most 1, the red induced subgraph has minimum degree at least 1, and the red induced subgraph is P4-free. The authors conclude that the obstruction to crumby colorability already occurs at treewidth 2, even under 2-connectivity.

Significance. If the counterexamples are correctly constructed and verified, the result is significant because it supplies concrete, small obstructions inside the well-structured class of partial 2-trees, thereby sharpening the boundary between positive results for K4-minor-free graphs and the known general counterexamples. The explicit provision of the graphs themselves (rather than an existence proof) is a strength that permits independent checking.

major comments (1)
  1. [section on the 40-vertex graph] Section presenting the 40-vertex counterexample: the manuscript asserts that this graph admits no crumby coloring, yet supplies no description of the verification procedure. Exhaustive enumeration over 2^40 partitions is impossible; therefore the claim requires an explicit account of the algorithm (SAT encoding, pruned backtracking, or case analysis) together with its correctness argument or implementation details. Without this, the central disproof cannot be confirmed from the text.
minor comments (1)
  1. [abstract] The abstract states the existence of the two graphs but gives no hint of the verification method used for the larger example; a single sentence indicating the computational approach would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful review and for highlighting the need to document the verification procedure for the 40-vertex counterexample. We will revise the manuscript to address this point.

read point-by-point responses

  1. Referee: Section presenting the 40-vertex counterexample: the manuscript asserts that this graph admits no crumby coloring, yet supplies no description of the verification procedure. Exhaustive enumeration over 2^40 partitions is impossible; therefore the claim requires an explicit account of the algorithm (SAT encoding, pruned backtracking, or case analysis) together with its correctness argument or implementation details. Without this, the central disproof cannot be confirmed from the text.

    Authors: We agree that an explicit description of the verification is required for reproducibility. The absence of a crumby coloring in the 40-vertex graph was established via a SAT encoding: each vertex is assigned a Boolean variable for its color; clauses enforce that (i) no blue vertex has degree greater than 1 in the blue subgraph, (ii) every red vertex has degree at least 1 in the red subgraph, and (iii) the red subgraph is P4-free. The resulting CNF instance was solved with the Glucose SAT solver and returned UNSAT. Correctness of the encoding was cross-validated by applying the identical procedure to the 18-vertex counterexample (where exhaustive enumeration over 2^18 colorings independently confirms the result) and by checking that the solver correctly identifies known crumby colorings on smaller partial 2-trees. In the revised manuscript we will insert a new subsection detailing the variable and clause construction, the solver configuration, running time (under 30 seconds on commodity hardware), and a link to the publicly archived source code and graph files. revision: yes

Circularity Check

0 steps flagged

No circularity; explicit counterexamples with independent verification

full rationale

The paper constructs two specific graphs (18-vertex connected subcubic partial 2-tree and 40-vertex 2-connected subcubic partial 2-tree) and asserts they are K4-minor-free yet admit no crumby coloring, directly disproving the conjecture. No equations, parameters, or derivations appear that reduce by construction to self-definitions, fitted inputs, or self-citations. The non-existence claim is a property of the concrete objects rather than a renaming or ansatz smuggled via prior work, rendering the argument self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests only on standard background definitions from graph theory; no free parameters are introduced, no new entities are postulated, and the axioms invoked are the usual ones for minors, degree bounds, and colorings.

axioms (1)
  • standard math Standard definitions of K4-minor-free graphs, subcubic graphs, partial 2-trees, and crumby colorings.
    The paper uses these established concepts without new or ad-hoc axioms.

pith-pipeline@v0.9.0 · 5496 in / 1221 out tokens · 27476 ms · 2026-05-08T16:39:15.071302+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

7 extracted references · 7 canonical work pages

  1. [1]

    J. Barát. Decomposition of cubic graphs related to Wegner’s conjecture.Discrete Mathematics, 342(5):1520–1527, May 2019. URL:https://www.sciencedirect.com/science/article/pii/ S0012365X19300366,doi:10.1016/j.disc.2019.01.025

    work page doi:10.1016/j.disc.2019.01.025 2019

  2. [2]

    Barát, Z

    J. Barát, Z. L. Blázsik, and G. Damásdi. Crumby colorings — Red-blue vertex partition of sub- cubic graphs regarding a conjecture of Thomassen.Discrete Mathematics, 346(4):113281, Apr

    work page

  3. [3]

    URL:https://www.sciencedirect.com/science/article/pii/S0012365X22004873, doi:10.1016/j.disc.2022.113281

    work page doi:10.1016/j.disc.2022.113281 2022

  4. [4]

    Bellitto, T

    T. Bellitto, T. Klimošová, M. Merker, M. Witkowski, and Y. Yuditsky. Counterexamples to Thomassen’s Conjecture on Decomposition of Cubic Graphs.Graphs and Combinatorics, 37(6):2595–2599, Nov. 2021.doi:10.1007/s00373-021-02380-z. 8

    work page doi:10.1007/s00373-021-02380-z 2021

  5. [5]

    S. G. Hartke, S. Jahanbekam, and B. Thomas. The chromatic number of the square of subcubic planar graphs, Apr. 2016. arXiv:1604.06504 [math]. URL:http://arxiv.org/abs/1604.06504, doi:10.48550/arXiv.1604.06504

    work page Pith review doi:10.48550/arxiv.1604.06504 2016

  6. [6]

    Thomassen

    C. Thomassen. The square of a planar cubic graph is 7-colorable.Journal of Combinatorial Theory, Series B, 128:192–218, Jan. 2018. URL:https://www.sciencedirect.com/science/ article/pii/S0095895617300783,doi:10.1016/j.jctb.2017.08.010

    work page doi:10.1016/j.jctb.2017.08.010 2018

  7. [7]

    G. Wegner. Graphs with given diameter and a coloring problem. Technical report, University of Dortmund, 1977. URL:http://hdl.handle.net/2003/34440. 9

    work page 1977