{"id":"1ccc2cf0-710b-479f-94b4-294df16f5ebe","arxiv_id":"2507.03244","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Every graph with no K_7^∨-minor (K_7 with two edges sharing an endpoint deleted) is 6-colorable, proved via a new extremal theorem for 4-connected graphs.","lead":"The paper proves that every graph that avoids a specific near-complete 7-vertex graph as a minor can still be colored with 6 colors, a step toward Hadwiger's conjecture. It strengthens an earlier result by removing one of two forbidden minors.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Claim 4.4 is underjustified: the Moser-spindle classification is delegated, and the step from a rooted C5-model to a K∨_7 minor is not demonstrated, since a C5-model alone does not produce the required 19-edge graph.","rationale":"Reader correctly flags the finite case analyses, but the more specific gap is the final inference in Claim 4.4. A rooted C5-model only guarantees a 5-cycle after contraction; K∨_7 requires 19 of 21 possible edges. The proof does not show how the bags add the remaining edges or how u'_3 connects to them. This is not a matter of external consensus; it is an internal gap in the written argument. The rest of the proof (Theorem 6, clique counting) appears coherent, and no fatal error was found elsewhere. Hence the verdict should remain CONDITIONAL: the theorem may be true, but Claim 4.4 needs a full derivation or machine verification before the proof is complete. My concern partially overlaps the reader's weakest_assumption but focuses on a distinct step.","tokens_in":17089,"tokens_out":36908,"duration_ms":403757,"concrete_test":"Write a short exhaustive program that enumerates all 7-vertex graphs H with α(H) ≤ 2 and ω(H) ≤ 3; for each such H, construct the graph G' obtained by identifying v, u'_3, and u'_4, and check that every 6-coloring satisfying the stated distinctness conditions yields, via the Kempe-chain C5-model, a minor on {v,u'_3} plus the five bags that contains K∨_7. If any H or coloring fails, Claim 4.4 is false. As a first step, verify the classification by checking that each enumerated H contains the Moser spindle as a subgraph.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The linchpin of Section 4 is Claim 4.4, which produces the 5-cliques feeding Claims 4.5–4.10. Its proof has two unverified parts. First, it asserts without derivation that every 7-vertex graph H with α(H) ≤ 2 and ω(H) ≤ 3 contains a Moser spindle, citing [KT05, Section 2] and 'moderately routine case analysis'. Second, and more seriously, the final inference is not justified: after contracting vu'_4 and vu'_3 and 6-coloring G', Theorem 14 supplies a (u1,...,u5)-rooted C5-model in G \\ {v,u'_3,u'_4}. Contracting its five bags yields a C5 on the five bag-vertices. Together with v and u'_3 this gives seven vertices, but K∨_7 has 19 edges, so the five bag-vertices need at least eight further edges among themselves and u'_3 needs to be adjacent to all but at most two of them. The proof gives no reason why the Kempe-chain bags provide these edges. The bags are contained in G \\ {v,u'_3,u'_4} and may include vertices outside N[v], so u'_3's adjacencies to the bags are not controlled by the Moser-spindle structure inside N(v). Thus the claimed K∨_7 minor is not established. Since Claim 4.4 is essential for the existence of enough 5-cliques, this is a load-bearing gap in the proof of Theorem 4.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves that every graph with no K_7^∨-minor is 6-colorable, strengthening Jakobsen's theorem that excluded both K_7^∨ and K_7^=. The proof follows the contraction-critical framework: assuming a minor-minimal 7-chromatic counterexample, it establishes an extremal theorem (Theorem 6) asserting that every 4-connected graph with |E| ≥ 4|V| − 8 has a K_7^∨-minor unless it is K_{2,2,2,2}. This is used to show that the counterexample has many degree-7 vertices, whose closed neighborhoods are claimed to contain 5-cliques (Claim 4.4). The final stage analyzes the intersections of these 5-cliques to force a K_7 minor, contradicting the minor-minimality. The argument imports several external theorems (RST93, Jørgensen, KT05, KLNZ05, Mader, Dirac, Kriesell–Mohr) and contains several finite case analyses that are sketched rather than fully derived.","tokens_in":17318,"tokens_out":14448,"duration_ms":149483,"significance":"If correct, the main theorem is a genuine strengthening of a 1971 result of Jakobsen and brings the t = 7 case of Hadwiger's conjecture closer to resolution. Theorem 6, the new extremal result for K_7^∨-minors in 4-connected graphs, is of independent interest and parallels Jørgensen's theorem for K_{4,4}-minors. The paper is self-contained modulo published theorems, makes no use of fitted parameters, and its central claim is concrete and falsifiable. The main weaknesses are that several load-bearing case analyses are only sketched or delegated, and one inference in Claim 4.4 appears, as written, to be unsupported; these issues must be repaired before the result can be considered established.","major_comments":[{"comment":"The conclusion 'Contracting the bags of this model, we obtain a minor of G which induces K_7^∨ on N[v] − {u'_4}' does not follow from the preceding argument. A rooted C5-model guarantees only that, after contracting the five bags, the resulting vertices form a cycle; it does not guarantee that they form a K5. In K_7^∨, the five bag-vertices must be pairwise adjacent, giving 10 edges among them, whereas the C5-model supplies only the five cycle edges. The Kempe-chain bags may contain vertices outside N[v], so the adjacencies of u'_3 to the bags are not controlled by the Moser-spindle structure inside N(v). Together with the star from v, the edge count is at most 12 guaranteed edges plus the five cycle edges, far short of the 19 edges of K_7^∨; no argument is given for the missing edges. This is load-bearing because Claim 4.4 is what produces the 5-cliques used in Claims 4.5–4.10.","section":"Section 4, Claim 4.4 (final paragraph)"},{"comment":"The assertion that every 7-vertex graph H with α(H) ≤ 2 and ω(H) ≤ 3 contains a subgraph isomorphic to the Moser spindle is justified only by a reference to '[KT05, Section 2]' and the phrase 'moderately routine case analysis'. This finite classification is not derived in the paper, and it is the only route from a degree-7 vertex to a 5-clique. The authors should either supply the complete case analysis or provide a precise statement and location of a lemma in KT05 that proves exactly this classification; as written, the claim cannot be independently verified by the reader.","section":"Section 4, Claim 4.4 (first paragraph)"},{"comment":"Each of the five cases for the complement H of G[N(v)] is dismissed in a single sentence of the form 'contracting ... we obtain a minor inducing K_7^∨ on N[v]'. Because Claim 3.11 is essential for the proof of Theorem 6, these five finite verifications are load-bearing. The description of the contractions is too terse to confirm that the resulting minor indeed has all edges of K_7^∨; a missed adjacency pattern in any of the five cases would invalidate the extremal theorem. The authors should describe the resulting minor explicitly for each case, or provide a machine-checkable certificate.","section":"Section 3, Claim 3.11"}],"minor_comments":[{"comment":"The displayed equation contains an arithmetic error: after obtaining |E(G)| ≤ 3|B| − 2 = 3(|V(G)| − 2) − 2, the text writes '≤ 3|B| − 8', which is inconsistent. The intended bound is |E(G)| ≤ 3|V(G)| − 8; this should be corrected.","section":"Section 2, Lemma 9, equation (1)"},{"comment":"In the case |Z| = 1, the sentence 'L1 ∪ (L2 ∩ L3) induces a supergraph of K_7^∨' cannot be correct, since the set has only six vertices; it should read K_6^∨ (or K_7^∨ should be replaced by K_6^∨). The argument itself is valid because the unique vertex in (L2 ∩ L3) \\ L1 is adjacent to at least three vertices of the 5-clique L1.","section":"Section 4, Claim 4.10"},{"comment":"In the final case of Claim 3.15, the notation 'y ∈ B′ − A′' is used, but the sets A′ and B′ have not been introduced in that paragraph; this makes the argument difficult to follow and should be clarified.","section":"Section 3, Claim 3.15, third bullet"},{"comment":"The phrase 'It remains to show exclude the case' is missing the word 'to'; it should read 'It remains to show how to exclude the case'.","section":"Section 4, Claim 4.10, first sentence"},{"comment":"The description of reference [RST23] as discussing 'minor minimal non-7-colorable graphs with no K7-minor' appears to be inaccurate; the cited paper concerns 8-contraction-critical graphs with no K7 minor. The sentence should be corrected.","section":"Section 1, Introduction"}],"recommendation":"major_revision","confidential_remarks":"The gap in Claim 4.4 is not a minor presentation issue: the final inference from a rooted C5-model to a K_7^∨ minor is, as written, mathematically unsupported, and the claim is central to the proof of Theorem 4. I would ask the authors to supply a complete derivation of that step or to replace it with a correct argument producing the needed 5-cliques. In addition, the finite classifications in Claim 3.11 and in the first part of Claim 4.4 should be fully verified, ideally with an explicit or machine-checked case analysis, before the paper can be accepted. The overall strategy and the extremal Theorem 6 are plausible and significant, so I believe the issues are fixable within the scope of a revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This paper has a genuinely new result: Theorem 4 strengthens Jakobsen by dropping the K=7 exclusion, and the extremal Theorem 6 is a useful tool in its own right. But the final step of Claim 4.4, where a rooted C5-model is converted into a K7^∨ minor, has a real gap that I don't think is merely cosmetic.\n\nWhat's new: the rooted-minor toolkit is extended, notably Lemma 12, which upgrades Jørgensen's Lemma 17 to a K*_{4,2}-model. The proof of Theorem 6 is long but structurally transparent, and the case analysis in Claims 3.1–3.15 is mostly checkable. The ending of Theorem 4 (clique counting via Claims 4.5–4.10) is elegant and would be a nice payoff if the foundation holds. Credit where due: the density argument, the use of Theorem 14, and the overall strategy are all serious pieces of work.\n\nSoft spots: the reader flagged omitted finite verifications in Claim 3.11 and Claim 4.4, plus typos in Lemma 9, equation (1), and Claim 4.10. Those are addressable. More importantly, I share the stress-test's concern about Claim 4.4. The proof asserts that contracting the bags of the C5-model gives K7^∨ on N[v]−{u'4}, but that needs the bags to have many pairwise adjacencies. The model only guarantees the five cycle edges. The Moser spindle structure gives some edges among the roots, but the bags are not confined to N[v], and u'3's connections to the bags are only through its neighbors among the roots. I sketched a plausible labeling of the Moser spindle and got only 11 edges among the six non-v vertices instead of the 13 needed. Unless there is a hidden lemma about Kempe chains supplying the missing adjacencies, the step is unjustified. This is not a routine omission—it's load-bearing, because all of Section 4 rests on Claim 4.4 producing the 5-cliques.\n\nWho it's for: this is squarely for graph-minors and graph-coloring researchers. It deserves a serious referee, and I would send it to a top combinatorics journal, but with a strong request: the authors must either write out the missing verification in Claim 4.4 or replace that step with a proper lemma. As it stands, the proof of Theorem 4 is incomplete, even though the main idea is plausible and the extremal theorem is valuable on its own. Recommendation: send to peer review, conditional on a substantive revision of Claim 4.4.","headline":"A genuinely new strengthening of Jakobsen's theorem and a reusable extremal density result, but the proof of Claim 4.4 has a load-bearing gap that needs a substantive fix.","tokens_in":17978,"tokens_out":16743,"would_cite":false,"duration_ms":177297,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15","05C83","05C35"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every graph with no $K_7^{\\vee}$-minor is 6-colorable.","keywords":["Hadwiger's conjecture","graph minors","6-colorability","K7∨-minor","rooted minors","contraction-critical graphs","Moser spindle","extremal graph theory"],"falsifier":"A direct counterexample: a single 7-chromatic graph with no $K_7^{\\vee}$-minor would refute Theorem 4; a concrete search target would be any 7-contraction-critical graph on at least 18 vertices whose degree-seven neighborhoods all pass the Claim 4.4 case analysis but whose 5-clique family nevertheless satisfies Claim 4.10. Alternatively, an exhaustive computer check of all 4-connected graphs on 9--12 vertices looking for one with $|E| \\ge 4|V| - 8$, not isomorphic to $K_{2,2,2,2}$, and no $K_7^{\\vee}$-minor would settle Theorem 6.","tokens_in":16785,"feed_emoji":"🎨","tokens_out":12258,"duration_ms":123454,"temperature":0.7,"pith_summary":"The paper proves that any graph avoiding the graph $K_7^{\\vee}$ as a minor — the complete graph on seven vertices with two edges sharing an endpoint removed — can be properly colored with six colors. This is a strengthening of the earlier result that required excluding both $K_7^{\\vee}$ and the matching-deletion graph $K_7^{=}$; here the single forbidden minor suffices. The argument assumes a hypothetical 7-chromatic counterexample, then uses a new extremal theorem to show it must be edge-dense and 4-connected, with many degree-seven vertices. Each such vertex forces a 5-clique in its neighborhood, and the intersection pattern of those 5-cliques is shown to be impossible. Consequently, any graph needing seven colors must contain $K_7^{\\vee}$ as a minor, a concrete step toward the t=7 case of Hadwiger's conjecture.","feed_headline":"Graphs missing a seven-vertex near-clique need only six colors","feed_subtitle":"The result forces every seven-color-needing graph to harbor the near-complete K7∨ minor, a step toward Hadwiger's t=7 case.","key_machinery":"The main working object is the rooted model: a family of disjoint connected subgraphs (bags), each containing a prescribed root vertex, with edges prescribed between bags; contracting the bags produces a desired minor. The proof's engine is a refined rooted-model lemma: an internally 4-connected graph with no rooted $K^*_{4,2}$-model has at most $4|V| - 10$ edges, derived from trisection and crossing-path theorems and from prior extremal rooted-minor lemmas. In the coloring half, the decisive combinatorial device is the intersection pattern of 5-cliques: any three distinct 5-cliques must intersect in sizes 2, 2, 1, which forces the clique-intersection graph to be bipartite even though the proof needs it to be non-bipartite and large.","core_discovery":"The central theorem, Theorem 4, asserts that every graph with no $K_7^{\\vee}$-minor is 6-colorable; equivalently, every 7-chromatic graph contains $K_7^{\\vee}$ as a minor. The load-bearing subclaim, Theorem 6, is an extremal statement: every 4-connected graph $G$ with $|E(G)| \\ge 4|V(G)| - 8$ has a $K_7^{\\vee}$-minor unless $G \\simeq K_{2,2,2,2}$. The proof obtains this by taking a minor-minimal counterexample, eliminating 4-separations and vertices of degree five and seven, and then ruling out the surviving degree-six case through a planar/separation argument. On the coloring side, the paper shows a 7-contraction-critical graph would have at least 18 degree-seven vertices, each living in a 5-clique, and then proves the family of such 5-cliques cannot satisfy the required intersection constraints. Therefore no counterexample exists.","pith_inferences":["Editorial: the same rooted-model toolkit may prove an analogous 5-connected extremal theorem for $K_7^{=}$ at the threshold $4|V|-9$, which the paper states as Conjecture 20; if that holds, the full delete-two-edges family would be covered.","Editorial: the 'moderately routine case analysis' in Claim 4.4 is a finite verification gap; a machine-certified enumeration of all seven-vertex neighborhoods with no independent set of size three and no 4-clique would independently settle that step.","Editorial: because Theorem 6 explicitly isolates $K_{2,2,2,2}$ as the only exception at $4|V|-8$, edge modifications of this graph (adding or deleting a few edges) are natural test cases for whether the threshold is tight in the 4-connected class.","Editorial: the 5-clique intersection theorem suggests a transferable principle—large families of nearly disjoint large cliques in critically colored graphs force complete minors—whose extension to $K_8$ and $K_9$ deletion-minor colorability could shorten the analogous proofs."],"forward_implications":["Every 7-chromatic graph contains $K_7^{\\vee}$ as a minor, so any potential counterexample to Hadwiger's conjecture for $t=7$ would have to contain this near-complete minor even while avoiding $K_7$.","Theorem 6 gives a sharp edge threshold: a 4-connected graph with $|E(G)| \\ge 4|V(G)| - 8$ is either $K_{2,2,2,2}$ or has a $K_7^{\\vee}$-minor; consequently, in the 4-connected $K_7^{\\vee}$-minor-free setting the edge count is at most $4|V| - 9$ apart from that one exception.","A 7-contraction-critical graph that avoids $K_7^{\\vee}$ would need at least 18 vertices of degree seven, and each of those vertices must lie in a 5-clique; the paper shows this configuration is structurally impossible.","The earlier 6-colorability theorem of Jakobsen is upgraded: excluding $K_7^{\\vee}$ alone, without excluding the two-edge-matching deletion $K_7^{=}$, is enough to force 6-colorability."],"supporting_citations":[{"why":"Proves the base colorability when both K7∨ and K7= are forbidden; Theorem 4 removes the second exclusion.","marker":"[Jak71]"},{"why":"Supplies the Moser-spindle neighborhood analysis in Section 2, Lemma 17 on three 5-cliques forcing a K7 minor, and the overall contraction-critical strategy this paper extends.","marker":"[KT05]"},{"why":"Provides the rooted K4^- and K4,2-model extremal lemmas and the 4-connected edge-bound theorem that Theorem 6 refines.","marker":"[Jø94]"},{"why":"Provides the trisection theorem and the crossing-paths theorem used in Lemma 9 and Claim 3.15 to control separations and build rooted models.","marker":"[RST93]"},{"why":"Gives the Kempe-chain-to-cycle-minor theorem used in Claim 4.4 to convert coloring obstructions into the required C5-model.","marker":"[KM19]"},{"why":"States the three-nearly-disjoint-cliques theorem used in Claim 4.7 to bound triple intersections of 5-cliques.","marker":"[KLNZ05]"},{"why":"Establishes that 7-contraction-critical graphs are 7-connected, giving the minimum-degree lower bound at the start of Section 4.","marker":"[Mad67]"},{"why":"Bounds independent sets in closed neighborhoods of contraction-critical graphs, used in Claim 4.4 to constrain the degree-seven neighborhood.","marker":"[Dir60]"}],"fun_headline_variants":["Near-K7-free graphs need only six colors","Six colors suffice for near-K7-free graphs","7-chromatic graphs always contain near-K7 minor","Every 7-color graph hides a near-K7 minor"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the finite check of all possible neighborhoods of a degree-seven vertex is exhaustive, leaving only one special seven-vertex configuration (the Moser spindle) in the no-4-clique case; if any configuration was missed, the proof that the counterexample has many 5-cliques would collapse.","fun_headline_variants_meta":{"raw":{"variants":["Near-K7-free graphs need only six colors","Six colors suffice for near-K7-free graphs","7-chromatic graphs always contain near-K7 minor","Every 7-color graph hides a near-K7 minor"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001486,"raw_usage":{"total_tokens":5899,"prompt_tokens":809,"completion_tokens":5090,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":425,"completion_tokens_details":{"reasoning_tokens":5028}},"tokens_in":425,"tokens_out":5090,"duration_ms":39765,"temperature":1.0,"reasoning_tokens":5028,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T20:18:25.052237+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A direct counterexample: a single 7-chromatic graph with no $K_7^{\\vee}$-minor would refute Theorem 4; a concrete search target would be any 7-contraction-critical graph on at least 18 vertices whose degree-seven neighborhoods all pass the Claim 4.4 case analysis but whose 5-clique family nevertheless satisfies Claim 4.10. Alternatively, an exhaustive computer check of all 4-connected graphs on 9--12 vertices looking for one with $|E| \\ge 4|V| - 8$, not isomorphic to $K_{2,2,2,2}$, and no $K_7^{\\vee}$-minor would settle Theorem 6.","supporting_citations":[],"review_version":1}