{"id":"d550f4e5-df62-4ae5-99cf-e248badbf389","arxiv_id":"1908.06697","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Thomassen's conjecture on good 2-colorings of 3-connected cubic graphs is false: infinitely many 3-connected cubic graphs admit no such coloring.","lead":"A team of graph theorists built infinite families of cubic graphs that break a coloring rule conjectured by Thomassen. The result removes a proposed shortcut to proving an older conjecture about coloring planar graphs with 7 colors.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Corollary 8's infinite 3-connected family depends on an unproved assertion that replacing an induced 6-cycle by H'' preserves 3-connectivity; H'' is only 2-connected and no terminal pairing is specified.","rationale":"The reader identified exactly the same load-bearing spot: the passage from the H'' no-good-coloring lemma to an infinite family of 3-connected cubic graphs relies on an unproved preservation of 3-connectivity. I agree that Theorem 7 is credible: the case analyses in Lemmas 5 and 6 are explicit and small enough to check, and the statement about subcubic graphs is independent of the 3-connected construction. The problem is solely with Corollary 8. The replacement claim is not automatic: H'' is stated to be only 2-connected, and no matching of the six degree-2 vertices is specified. In particular, if G−C has two components, the replacement graph's 3-connectivity reduces to whether H'' can connect the two terminal triples without any 2-cut; the paper gives no reason that it can. A conditional verdict is therefore the right level: the main construction of counterexamples to Thomassen's conjecture is not fully proved, but the flaw is a gap that may be repairable, not an observed contradiction. The recommended concrete test, checking H'' with a universal apex or exhaustively testing the replacement on small 3-connected cubic graphs, would settle whether the gap is merely missing proof or a genuine obstruction. If the test shows failures, the paper's central claim as stated would need a different construction; if it passes, only a written proof of the 3-connectivity preservation is missing. No other concern appears more load-bearing: the definition of good coloring, the gadget proofs, and the subcubic disproof are consistent and checkable.","tokens_in":3043,"tokens_out":14576,"duration_ms":149802,"concrete_test":"Add a universal vertex z joined to the six degree-2 vertices of H'' and test whether H''+z is 3-connected. If it is not, exhibit the 2-cut and construct a host graph G with an induced 6-cycle where the replacement induces that cut; this would falsify the pre-Corollary 8 assertion. If H''+z is 3-connected, use nauty to enumerate all 3-connected cubic graphs with an induced 6-cycle up to 14 vertices, replace C under all bijections from C to the six terminals, and verify that every resulting graph is 3-connected; any failure disproves the universal replacement claim.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central theorem (Theorem 7) is well-supported: any subcubic graph containing H'' has no good coloring. What is not supported is the transition to 3-connected cubic graphs in Corollary 8. The proof says only, 'Since H'' contains precisely six vertices of degree 2, it is possible to replace C by a copy of H'' so that the resulting graph is again 3-connected and cubic.' This is asserted, not proved. H'' itself is explicitly 2-connected (final paragraph), and the six degree-2 vertices are not assigned to the vertices of C by any specified rule. In a 3-connected cubic graph, an induced 6-cycle C can be separating: G−C can split into two components, each incident with three vertices of C (3-connectivity forces at least three attachments per side, and there are six total). After replacing C, all connections between those two sides route through H''. If H'' has a 2-vertex cut separating the terminals attached to one side from those attached to the other, the resulting graph has a 2-cut and is not 3-connected. No argument rules out such a cut. Thus the infinite family of 3-connected cubic counterexamples, the main claim against Thomassen's conjecture, is not established by the text. The disproof of Barát's conjecture for subcubic graphs does not rely on this step and appears sound.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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).","tokens_in":3352,"tokens_out":8542,"duration_ms":79686,"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":[{"comment":"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.","section":"Paragraph before Corollary 8"},{"comment":"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.","section":"Paragraph before Corollary 8"}],"minor_comments":[{"comment":"In condition (2), 'the the subgraph' contains a duplicated article and should read 'the subgraph'.","section":"Definition 1"},{"comment":"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.","section":"Introduction, paragraph 3"},{"comment":"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.","section":"Note after Theorem 7"}],"recommendation":"major_revision","confidential_remarks":"The core gadget result (Theorem 7) appears correct and directly disproves Barát's conjecture, which is a worthwhile result. The advertised disproof of Thomassen's conjecture, however, depends on an unproved and nontrivial 3-connectivity-preservation claim. This is a fixable gap if the authors can produce a proof or an explicit construction of infinitely many 3-connected cubic graphs containing H''. If the gap cannot be closed, the paper should be reframed around the subcubic disproof of Barát's conjecture, which would still be publishable but with a significantly weaker title and abstract."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The real contribution here is the H'' gadget and the forced-coloring lemmas. Lemma 5 and Lemma 6 are explicit, checkable case analyses and I could not find a hole. Theorem 7 follows cleanly: any subcubic graph containing H'' has no good coloring. That is a genuine, new result and it already disproves Barát's conjecture for subcubic graphs. The construction is not a routine variant of known gadgets; the propagation of red/blueness through the three copies of H' is clever and non-obvious. The citation pattern is appropriate — Wegner, Thomassen, Hartke et al., and Barát are all cited for exactly what they did.\n\nThe soft spot is exactly the one the stress test flags. Corollary 8 is not established. The text says that any induced 6-cycle C in a 3-connected cubic graph can be replaced by H'' so the result is again 3-connected, but no proof is given. H'' itself is only 2-connected, and the six degree-2 vertices are never paired with the vertices of C. If C is a separating cycle, the two sides of G-C each attach to three vertices of C; replacing C with H'' routes all inter-side connections through a 2-connected gadget. If H'' has a 2-vertex cut separating the terminals on one side from those on the other, the new graph has a 2-cut and is not 3-connected. The paper does not rule that out. This is not a minor omission because the infinite 3-connected family is the advertised disproof of Thomassen's conjecture. Without it, the paper refutes the weaker Barát conjecture only, which is still a solid result.\n\nI want to be clear: this is not a takedown. The central gadget theorem appears correct and the gap is probably fixable — one can construct an explicit infinite family of 3-connected cubic graphs containing H'' or prove a careful replacement lemma specifying which degree-2 vertices attach where. The paper is short, readable, and the main proof is self-contained. A serious referee should see it; the result is worth having in the literature even with a rewrite of the last section.\n\nRecommendation: send to peer review. Ask the authors to prove or repair the 3-connectivity claim in Corollary 8, and meanwhile the subcubic counterexample to Barát stands on its own.","headline":"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.","tokens_in":3844,"tokens_out":1833,"would_cite":true,"duration_ms":18919,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15","05C40"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["good coloring","cubic graphs","subcubic graphs","3-connected graphs","Thomassen's conjecture","Barát's conjecture","graph decomposition","counterexample"],"falsifier":"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.","tokens_in":2868,"feed_emoji":"🎨","tokens_out":12144,"duration_ms":119452,"temperature":0.7,"pith_summary":"The paper sets out to disprove Thomassen's conjecture, which said that every 3-connected cubic graph on at least 8 vertices can be split into a blue subgraph of maximum degree at most 1 and a red subgraph in which every vertex has degree at least 1 and no path has four vertices. Such a good coloring was a proposed route to proving Wegner's conjecture that the square of every planar cubic graph is 7-colorable. The paper builds a 48-vertex gadget $H''$ with the property that no subcubic graph containing $H''$ admits a good coloring. Since $H''$ can be inserted into infinitely many 3-connected cubic graphs, the conjecture is false; the same construction also refutes Barát's stronger conjecture that every subcubic graph on at least 7 vertices has a good coloring.","feed_headline":"A 48-vertex gadget disproves Thomassen's cubic-graph conjecture","feed_subtitle":"The 48-vertex gadget blocks every valid red-blue split, so the proposed proof route to Wegner's theorem fails.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"It states the conjecture under attack and proves that a good coloring yields a 7-coloring of the square; this is the conjecture the paper refutes.","marker":"[3]"},{"why":"It proves the conjecture for generalized Petersen graphs and formulates the stronger subcubic conjecture that the paper also refutes.","marker":"[1]"},{"why":"It gives the independent proof of the square-coloring theorem and the reduction showing that a minimal counterexample would be cubic and 3-connected.","marker":"[2]"},{"why":"It introduces the square-coloring problem whose proposed proof route passes through good colorings.","marker":"[4]"}],"fun_headline_variants":["Local 48-vertex obstruction refutes Thomassen's decomposition conjecture","48-vertex gadget topples Thomassen's cubic coloring conjecture","Infinite counterexample family breaks Thomassen's cubic graph conjecture","Cubic graph conjecture fails: 48-vertex gadget blocks colorings"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Local 48-vertex obstruction refutes Thomassen's decomposition conjecture","48-vertex gadget topples Thomassen's cubic coloring conjecture","Infinite counterexample family breaks Thomassen's cubic graph conjecture","Cubic graph conjecture fails: 48-vertex gadget blocks colorings"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001011,"raw_usage":{"total_tokens":4209,"prompt_tokens":819,"completion_tokens":3390,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":435,"completion_tokens_details":{"reasoning_tokens":3316}},"tokens_in":435,"tokens_out":3390,"duration_ms":25765,"temperature":1.0,"reasoning_tokens":3316,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:37:41.302788+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Thomassen","cited_arxiv_id":null,"evidence_quote":"It states the conjecture under attack and proves that a good coloring yields a 7-coloring of the square; this is the conjecture the paper refutes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It proves the conjecture for generalized Petersen graphs and formulates the stronger subcubic conjecture that the paper also refutes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It gives the independent proof of the square-coloring theorem and the reduction showing that a minimal counterexample would be cubic and 3-connected."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It introduces the square-coloring problem whose proposed proof route passes through good colorings."}],"review_version":1}