REVIEW 2 major objections 3 minor 4 references
Counterexamples to Thomassen's conjecture on decomposition of cubic graphs
T0 review · 2 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read Thomassen's conjecture that every 3-connected cubic graph on at least 8 vertices has a good coloring is false: a 48-vertex gadget $H''$ blocks good colorings in every subcubic graph containing it.
desk verdict The H'' gadget and the proof that subcubic graphs containing it have no good coloring are solid and already refute Barát's conjecture, but the infinite family of 3-connected cubic counterexamples to Thomassen rests on an unproved 3-connectivity claim that needs a real fix. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the nested gadget chain $H \subset H' \subset H''$. Here $H$ is an 8-cycle with chords $v_2v_6$ and $v_3v_7$; $H'$ is two disjoint copies of $H$ joined by two edges; $H''$ is three disjoint copies of $H'$ joined in a 6-cycle. Lemma 5 says that in any subcubic supergraph, not both endpoints of a copy of $H$ can be red, and a red endpoint that has a red internal neighbor forces two specific vertices to be blue. Lemma 6 lifts this to $H'$: exactly one of the two external endpoints is red, the other is blue, and the red endpoint demands a red neighbor outside the copy. The 6-cycle in $H''$ forces these local demands to propagate around a cycle and collide, producing the contradiction.
What would settle it
Take the gadget $H''$ and add one pendant leaf to each of its six degree-2 vertices; the resulting 54-vertex subcubic graph either has a good coloring or it does not. Enumerating all $2^{54}$ blue/red colorings, or solving the implied constraint-satisfaction problem, would settle Theorem 7: one satisfying coloring refutes the paper's central claim, and exhaustively finding none confirms the local obstruction. To test the infinite-family corollary instead, check whether replacing an induced 6-cycle in a 3-connected cubic graph by $H''$ ever destroys 3-connectivity; if it does for some host graph, Corollary 8 would need a different proof.
Extended reading notes
Core claim
The core discovery is a local obstruction to good colorings. The gadget $H$ is an 8-cycle with two chords; $H'$ is two copies of $H$ joined by two edges; $H''$ is three copies of $H'$ joined in a 6-cycle $C=v_0v_1x_0x_1y_0y_1$. The authors prove that if a subcubic graph $G$ contains $H''$ as a subgraph, then $G$ has no good coloring. The proof uses two forced-coloring lemmas: within each copy of $H$, at most one of the two external endpoints can be red, and within each copy of $H'$, exactly one endpoint is red, the other is blue, and the red endpoint must have a red neighbor outside that copy. Reading these constraints around the 6-cycle $C$ forces a contradiction. Because $H''$ has six degree-2 vertices, it can replace an induced 6-cycle in any 3-connected cubic graph, and the authors conclude that an infinite family of such graphs has no good coloring.
Load-bearing premise
The load-bearing premise is that replacing an induced 6-cycle in any 3-connected cubic graph by the gadget $H''$ always yields another 3-connected cubic graph; the paper asserts this without proof, and it is not automatic because $H''$ alone is only 2-connected before the external edges are added.
Editorial extensions
If this is right
- If the construction is sound, Thomassen's conjecture is false: there is no universal good coloring for all 3-connected cubic graphs on at least 8 vertices.
- Barát's stronger conjecture is also false, since the gadget $H''$ itself is subcubic and every subcubic graph containing it fails to have a good coloring.
- The gadget construction generalizes: any graph formed by gluing an odd number of copies of $H'$ into a cycle, as in $H''$, also cannot appear in a subcubic graph with a good coloring.
- The authors note that the same gadget yields an infinite family of 2-connected cubic planar graphs with no good coloring, so the obstruction is not an artifact of nonplanarity.
- Wegner's square-coloring theorem may still be true, but the proposed proof route through Thomassen's conjecture and good colorings cannot be universal.
Reading between the lines
- Beyond the paper, the parity of the number of $H'$ copies looks essential: Lemma 6 forces each copy to contribute one red endpoint on the connecting cycle, and an odd cycle of such forced red vertices is what creates the contradiction. A natural test would be to color graphs built from an even number of copies.
- The paper's infinite-family claim is most exposed at the step where an induced 6-cycle in a 3-connected cubic graph is replaced by $H''$; this replacement is asserted to preserve 3-connectivity without proof, so a reader relying on Corollary 8 should verify that preservation explicitly.
- Because $H''$ is planar and small, a computational search over cubic supergraphs of $H''$ could identify the smallest 3-connected cubic graph with no good coloring, sharpening the authors' closing question about whether the 3-prism is the only bad planar case.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces a notion of a 'good' 2-coloring of cubic graphs (blue subgraph has maximum degree at most 1; red subgraph has minimum degree at least 1 and contains no path on 4 vertices). It defines a sequence of gadgets H, H', H'' and proves, via elementary case analysis, that every subcubic graph containing H'' as a subgraph admits no good coloring (Theorem 7). Since H'' itself is a subcubic graph on 48 vertices, this disproves Barát's conjecture (Conjecture 3). The paper further claims (Corollary 8) that an infinite family of 3-connected cubic graphs can be obtained by replacing an induced 6-cycle in any 3-connected cubic graph by H'', thereby disproving Thomassen's conjecture (Conjecture 2).
Significance. Theorem 7 is a clean and apparently correct result: the proof is a finite case analysis, the lemmas are derived directly from the definition of a good coloring, and the argument is self-contained. The disproof of Barát's conjecture follows immediately and is a genuine contribution. However, the advertised main result against Thomassen's conjecture rests on the unproved replacement step in the paragraph before Corollary 8, which is load-bearing for the abstract and for the paper's title. If that step can be supplied with a rigorous proof or an explicit construction of infinitely many 3-connected cubic graphs containing H'', the paper would fully establish its main claim; as it stands, the submitted version only establishes a subcubic counterexample.
major comments (2)
- [Paragraph before Corollary 8] The assertion that replacing an induced 6-cycle C in any 3-connected cubic graph G by a copy of H'' yields a 3-connected cubic graph is not proved. This is not automatic: H'' is explicitly 2-connected (final paragraph), and the six degree-2 vertices of H'' are not specified, nor is any rule given for identifying them with the six neighbors of C. In a 3-connected cubic graph, an induced 6-cycle can separate G−C into two components with three attachments per side; if the chosen identification makes H'' have a 2-vertex cut separating the two sides, the resulting graph is not 3-connected. No argument rules out such a cut. Consequently Corollary 8 does not follow from Theorem 7, and the claimed infinite family of 3-connected cubic counterexamples to Thomassen's conjecture is not established.
- [Paragraph before Corollary 8] The sentence 'The smallest 3-connected cubic graph containing H'' can be obtained from H'' by adding three edges joining the vertices of degree 2' is also asserted without proof. It is not obvious that any (or some) pairing of the six degree-2 vertices produces a 3-connected graph, and no demonstration is provided. This is a secondary instance of the same missing 3-connectivity argument.
minor comments (3)
- [Definition 1] In condition (2), 'the the subgraph' contains a duplicated article and should read 'the subgraph'.
- [Introduction, paragraph 3] The sentence 'This motivated him to propose the following strengthening of Conjecture 3' should refer to Conjecture 2, not Conjecture 3, since Barát's conjecture is the strengthening of Thomassen's conjecture.
- [Note after Theorem 7] The statement that 'any graph formed by gluing odd number of copies of H' into a cycle as in H'' cannot appear as a subgraph of a subcubic graph with a good coloring' is made without proof. If kept, it should either be proved or explicitly marked as a remark/conjecture.
Circularity Check
No circularity: the good-coloring impossibility for H'' is derived from the definition of a good coloring by case analysis; the 3-connected family step is an unproved assertion, not a circular reduction.
full rationale
The derivation chain is self-contained. Definition 1 fixes what a good coloring is; Lemmas 5 and 6 are proved by local case analysis using only the three coloring rules (blue maximum degree at most 1, red minimum degree at least 1, no red P4) and the structure of the gadgets H, H', and H''. Theorem 7 then combines these local constraints on the central 6-cycle to force a contradiction. No fitted quantity is renamed as a prediction, no parameter is calibrated to the target result, and no load-bearing result is imported from the authors' own prior work. The citations to Thomassen, Wegner, Barát, and Hartke et al. supply only the conjectures being refuted and background motivation; the counterexample proof itself does not rely on them. The one substantive gap is Corollary 8: the paper asserts that replacing an induced 6-cycle in a 3-connected cubic graph by H'' preserves 3-connectivity, although H'' is 2-connected and no terminal pairing is specified. That is a correctness or completeness concern about an auxiliary construction, not a circularity: it does not make the theorem equivalent to its assumptions by construction. Therefore the circularity score is 0.
Assumptions & free parameters
assumptions (2)
- standard math Standard graph-theoretic definitions and basic facts about induced subgraphs, minimum degree, and paths are used throughout.
- ad hoc to paper Replacing an induced 6-cycle in a 3-connected cubic graph by H'' with an appropriate matching of its six degree-2 vertices yields a 3-connected cubic graph.
Cite this review
Pith. "Pith review of Counterexamples to Thomassen's conjecture on decomposition of cubic graphs." pith.science (2026). https://pith.science/paper/TLNJ2CX2
@misc{pith2026190806697,
author = {Pith},
title = {Pith review of: Counterexamples to Thomassen's conjecture on decomposition of cubic graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/TLNJ2CX2}},
note = {Machine review of arXiv:1908.06697}
}
read the original abstract
We construct an infinite family of counterexamples to Thomassen's conjecture that the vertices of every 3-connected, cubic graph on at least 8 vertices can be colored blue and red such that the blue subgraph has maximum degree at most 1 and the red subgraph minimum degree at least 1 and contains no path on 4 vertices.
Figures
Reference graph
Works this paper leans on
-
[1]
J. Bar´ at. Decomposition of cubic graphs related to Wegner’s conjecture. Discrete Mathematics, 342(5):1520 – 1527, 2019
work page 2019
-
[2]
S. G. Hartke, S. Jahanbekam, and B. Thomas. The chromatic number of the square of subcubic planar graphs. arXiv e-prints, Apr. 2016
work page 2016
- [3]
-
[4]
G. Wegner. Graphs with given diameter and a coloring problem. Technical Report, University of Dortmund , 1977. 4
work page 1977
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.