{"id":"d8d22612-7093-455e-ac0b-9e75eb651b84","arxiv_id":"1908.05597","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Graphs with no K_{s+1}-subdivision are clustered-colorable with O(s) colors, and several stronger variants hold under almost (≤1)-subdivision and minor-free assumptions.","lead":"This paper proves that graphs avoiding a subdivision of the complete graph on s+1 vertices can be colored with O(s) colors when same-colored clusters are only required to be small instead of single vertices. This is the first linear-in-s bound in a weakening of Hajós' conjecture, which is known to be false in its original proper-coloring form.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 6 hinges on Lemma 19, whose proof is omitted; if the 'identical' restricted version of Lemma 18 does not carry through, the O(s) bound is unsupported.","rationale":"The reader's CONDITIONAL verdict is appropriate, and my stress-test does not move it. The central claim, Theorem 6, is accept-shaped but not standalone: it depends on Lemma 19, whose proof is explicitly omitted, and on companion preprints [23,24] for Theorems 8 and 9 and Lemmas 10–13. The most load-bearing single point is Lemma 19, since it is the internal bridge from K_{s,t}-free restricted list-coloring to almost-subdivision-free restricted list-coloring; all of Theorem 20(2)–(4), including the theorem used for Theorem 6, pass through it. I found no evidence of circularity or fitting-to-data, and the rest of Lemma 16's proof is a serious parameter-free derivation. The questionable-looking inequality in Claim 18.1 is not a real mathematical flaw, because the case |N_G(v)∩Y1| > β′ is impossible when N_{Y1}(v)⊆P and β′ > s−1, but the written proof should say so. The proposed concrete test — writing out the restricted version of Lemma 18's proof and checking the two listed conditions — would settle whether the omitted proof is genuinely identical. If it is, the verdict can move toward ACCEPT; if not, the paper needs a substantive repair.","tokens_in":27706,"tokens_out":27294,"duration_ms":255214,"concrete_test":"Write out the full proof of Lemma 19 by taking the proof of Lemma 18 and adding 'restricted' to every list-assignment occurrence. Verify explicitly: (a) in the definitions of L′ and L*, every chosen subset is a subset of L(v) and hence of [β′+r′]; (b) the cardinality identity |L(v)| = β′+r′−|N_G(v)∩Y1| is used only for vertices with |N_G(v)∩Y1| ≤ β′−1, which for v∈V(C) is automatic because N_{Y1}(v)⊆P and |P| = s−1 < β′; (c) the faithfulness condition is invoked only at the equality |N_G(v)∩Y1| = β′, while the '>β′' case is replaced by 'impossible'. If every step carries over verbatim, Lemma 19 is established; if any step requires a color outside [β′+r′] or a non-restricted list size, the omission is a genuine gap that blocks Theorem 6.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 19 (Section 4) is stated and then dismissed with 'The proof is identical, so we omit it.' This lemma is the transfer mechanism that upgrades restricted list-coloring results for K_{s,t}-free graphs (Theorems 8, 9 and Lemma 16) to restricted faithful list-coloring results for graphs with no almost (≤1)-subdivision of K_{s+1}. Theorem 20(3) invokes Lemma 19, and Theorem 20(4) — which directly yields Theorem 6, the paper's headline first O(s) bound — is derived from Theorem 20(3) by taking H = K_{s+1}. Because the proof of Lemma 19 is absent, the reader cannot verify that every step of Lemma 18's proof survives the additional 'restricted' condition L(v)⊆[β′+r′]. In particular, the construction of the list assignments L′ and L* must preserve this containment, and the cardinality identity |L(v)| = β′+r′−|N_G(v)∩Y1| may only be applied when |N_G(v)∩Y1| ≤ β′−1. In Lemma 18's Claim 18.1, a second case with |N_G(v)∩Y1| > β′ is written out with a questionable inference; that case is in fact vacuous for v∈V(C) because N_{Y1}(v)⊆P and |P| = s−1 < β′. A restricted-version proof must state this vacuity explicitly rather than relying on the printed chain. If Lemma 19 fails, the chain from Lemma 16 to Theorem 6 collapses, and the central claim is unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves several clustered-coloring results in the direction of Hajós' conjecture. It introduces the notion of an almost (≤1)-subdivision of a graph and shows, among other things, that graphs of bounded treewidth with no such subdivision of K_{s+1} are s-choosable with bounded clustering (Theorem 1), that graphs with no H-minor and no such subdivision are (s+1)-colorable with bounded clustering (Theorem 2), and that graphs with no K_{s+1}-subdivision are (4s−5)-colorable with bounded clustering (Theorem 6). The proof strategy combines the authors' earlier clustered-coloring results for K_{s,t}-free graphs with a structure theorem of Liu and Thomas for graphs excluding a bounded-degree subdivision. A long reduction (Lemma 16) establishes a restricted list-coloring statement for K_{s,t}-free graphs with no H-subdivision, and a transfer lemma (Lemmas 18 and 19) is used to pass from the K_{s,t}-free setting to the setting of graphs with no almost (≤1)-subdivision of K_{s+1}.","tokens_in":28070,"tokens_out":10903,"duration_ms":94896,"significance":"If correct, Theorem 6 gives the first O(s) bound on the clustered chromatic number of graphs with no K_{s+1}-subdivision, settling the clustered analogue of Hajós' conjecture up to a constant factor. Theorems 1 and 2 also give best-possible or near-best-possible numbers of colors in their settings. The paper is carefully structured, and the long proof of Lemma 16 is written in a self-contained manner. However, the central Theorem 6 depends on Lemma 19, whose proof is omitted, and on structure theorems and companion-paper results that are not reproduced here. The manuscript therefore currently leaves a load-bearing verification to the reader.","major_comments":[{"comment":"The proof of Lemma 19 is omitted with the sentence 'The proof is identical, so we omit it.' This is a load-bearing step: Theorem 20(3) invokes Lemma 19, Theorem 20(4) follows from Theorem 20(3) with H=K_{s+1}, and Theorem 6 is then read off from Theorem 20(4). The transfer from restricted list-coloring results for K_{s,t}-free graphs to restricted faithful list-coloring results for graphs with no almost (≤1)-subdivision of K_{s+1} requires checking that the constructions of L′ and L* in the proof of Lemma 18 preserve the restricted condition L(v)⊆[β′+r′], and that the cardinality identities such as |L(v)|=β′+r′−|N_G(v)∩Y1| remain valid in the restricted setting. Because the proof is absent, the central O(s) bound of Theorem 6 cannot currently be verified from the manuscript alone. Please include the full proof or a detailed appendix that goes through the restricted case line by line.","section":"Section 4, Lemma 19"},{"comment":"In the proof of Claim 18.1, for a vertex v∈V(C) with |N_G(v)∩Y1|>β′, the manuscript asserts |N_G(v)∩P| > |N_G(v)∩Y1|. This inequality is not justified and is in fact false in general. Because C is disjoint from Y1, any neighbor of v in Y1 must lie in P, so N_G(v)∩Y1⊆P and the case is vacuous: |P|=s−1<β′. The proof should state this vacuity explicitly. This is not a fatal error in Lemma 18 as written, but it is precisely the kind of step that the omitted 'identical' proof of Lemma 19 must handle, and the manuscript currently leaves that verification unperformed.","section":"Section 4, Claim 18.1 in Lemma 18"}],"minor_comments":[{"comment":"The sentence 'This together with Lemma 15 complete the proof of Theorems 1, 2, 4 and 6' is inaccurate. Lemma 15 concerns graphs of maximum degree at most 1 and is used for Theorem 5 when d=1; it does not address Theorems 1, 2, 4 and 6. Moreover, the case s=2 is not covered by Theorem 20, which assumes s>2, and is not discussed. These small cases follow from the fact that graphs with no almost (≤1)-subdivision of K3 are forests, but they should be stated explicitly.","section":"Section 4, final paragraph"},{"comment":"The proof relies on Theorem 14 from [22] and on Theorems 8 and 9 and Lemmas 10–13 from the companion papers [23,24], none of which are reproduced. Please add a sentence indicating the publication status of these references so that the reader knows whether the dependency is on published work or on preprints under review.","section":"Introduction and Section 2.2"},{"comment":"The remark that graphs of arbitrarily high girth and chromatic number show that excluding finitely many subgraphs cannot ensure an upper bound is stated too quickly; high girth alone does not forbid all subdivisions of K_{s+1}. Please clarify the intended argument or rephrase the remark.","section":"Introduction, remark after Theorem 5"}],"recommendation":"major_revision","confidential_remarks":"The paper is a serious contribution if the companion results hold. The main obstacle is the omitted proof of Lemma 19, which is load-bearing for the headline O(s) bound in Theorem 6; a lemma of this length and centrality cannot be dismissed with 'the proof is identical' without a detailed verification. I also recommend that the editor confirm the availability and status of the companion papers [23,24] and of [22], since the present manuscript's theorems depend on them in an essential way."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Theorem 6 is the headline and it holds up as far as I can see: the first O(s) clustered coloring bound for graphs excluding a K_{s+1}-subdivision, improving the earlier O(s^2) proper-coloring bounds and matching the lower bound up to a constant factor. The almost (≤1)-subdivision condition and faithful list assignments are genuinely useful strengthenings, and Theorems 1–5 are nontrivial consequences, not afterthoughts.\n\nThe paper is well-structured. Section 3's Lemma 16 is a long but mostly readable reduction from the Liu–Thomas structure theorem for excluded subdivisions. Section 4's Lemma 18 is the technical core, and its proof is detailed and coherent. I did not find a direct mathematical error.\n\nThe soft spots are what you'd expect from a paper at the frontier of its own series. Lemma 19, which transfers Lemma 18 to restricted list assignments, is stated with 'the proof is identical, so we omit it.' That is a real omission because Lemma 18's proof is long enough that 'identical' is not a trivial assertion. A referee should ask for the restricted proof or at least a clear statement of why each step survives the condition L(v)⊆[β+r]. The stress-test note about Claim 18.1 identifies a line that looks wrong on its face: the case |NG(v)∩Y1|>β' is actually vacuous for v∈V(C), since NG(v)∩Y1⊆P and |P|=s−1<β'. The printed chain is misleading, but the case being vacuous means it is harmless. A revision should fix that line.\n\nThe other caveat is that the proof leans heavily on Theorem 14 from Liu–Thomas and on Theorems 8–9 plus Lemmas 10–13 from the companion preprints [23,24]. These are not reproved here. That is acceptable in a series, but a referee needs to verify those imports. The self-citation has real content, not circularity.\n\nOverall the central claim is likely correct. The bound is interesting, the framework is reusable, and the writing is careful. The paper deserves a serious referee; I would recommend acceptance after the authors supply Lemma 19's proof and clean up the vacuous case.","headline":"First O(s) clustered coloring bound for K_{s+1}-subdivision-free graphs, built on a clever transfer lemma whose omitted restricted version is the only real gap.","tokens_in":28627,"tokens_out":4166,"would_cite":true,"duration_ms":40377,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15","05C83"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every graph with no subdivision of $K_{s+1}$ is colorable with $4s-5$ colors and bounded monochromatic components.","keywords":["Hajós conjecture","clustered coloring","graph subdivisions","list coloring","monochromatic components","treewidth","graph minors","tangles"],"falsifier":"For some fixed $s$ and arbitrarily large $\\eta$, construct a graph $G$ with no $K_{s+1}$-subdivision such that every coloring with at most $4s-5$ colors has a monochromatic component with more than $\\eta$ vertices; such a graph would directly disprove Theorem 6, the paper's central claim.","tokens_in":27505,"feed_emoji":"🎨","tokens_out":9475,"duration_ms":93636,"temperature":0.7,"pith_summary":"The paper proves that Hajós' conjecture, though false in its original form, holds up to a constant factor once each color class is allowed to split into components of bounded size. Concretely, for every $s$ there is an integer $\\eta$ such that every graph containing no subdivision of the complete graph $K_{s+1}$ admits a coloring with at most $4s-5$ colors in which every monochromatic component has at most $\\eta$ vertices. This is the first $O(s)$ bound for these graphs, whereas the original conjecture fails because some such graphs need roughly $s^2/\\log s$ colors when components must be single vertices. The same approach yields stronger results for bounded-treewidth graphs, for graphs with an excluded minor, and for graphs with an excluded subdivision of a bounded-degree graph, all with bounded clustering.","feed_headline":"Clustered Hajós conjecture: O(s) colors suffice","feed_subtitle":"Allow each color class to decompose into bounded pieces, and 4s-5 colors are enough for every K_{s+1}-subdivision-free graph.","key_machinery":"The central objects are clustered colorings, in which every monochromatic component has bounded size, and almost $(\\le 1)$-subdivisions, where at most one edge of the subdivided graph is subdivided more than once. The proof machinery is a list-coloring framework built around a distinguished set $Y_1$ of vertices whose lists have size one; a 'progress' operation moves vertices into $Y_1$ while pruning the lists of their neighbors. The deepest input is a tangle-based structure theorem for graphs excluding a fixed bounded-degree subdivision: any large tangle controlling a large clique minor forces a small exceptional set $Z$ such that every vertex outside $Z$ lies on the small side of a low-order separation. These tools split the graph into smaller pieces, color each piece by induction, and glue the colorings so that every monochromatic component stays bounded.","core_discovery":"The central discovery is that the obstruction that kills Hajós' conjecture—the chromatic number of $K_{s+1}$-subdivision-free graphs can grow like $s^2/\\log s$—disappears when monochromatic components are allowed to be large but bounded. The main theorem states that for each $s$ there exists $\\eta$ such that every graph with no $K_{s+1}$-subdivision has a coloring with at most $\\max\\{4s-5,1\\}$ colors and every monochromatic component has at most $\\eta$ vertices. The proof proceeds through a stronger family of statements about graphs avoiding almost $(\\le 1)$-subdivisions of $K_{s+1}$, using list-coloring with a distinguished set of precolored vertices and a structure theorem that confines large tangle structure to a small exceptional set. The final $O(s)$ bound is the first linear upper bound on the clustered chromatic number of $K_{s+1}$-subdivision-free graphs.","pith_inferences":["A likely next step is to make the clustering bound explicit and small: all $\\eta$ values in the theorems come from iterated functions and are not evaluated, so the theorem establishes existence but not practical colorings.","The method indicates that linear clustered colorings may extend to graphs excluding a subdivision of any fixed graph $H$, with constants depending only on $|V(H)|$ and $\\Delta(H)$, not just to complete graphs; the almost-$(\\le 1)$-subdivision statements are evidence that the decomposition is robust.","Testing the small case $s=4$ could sharpen the constant: if the $11$-color bound for $K_5$-subdivision-free graphs could be improved, the constant $4$ in $4s-5$ is not optimal, while a lower-bound example would identify the true linear rate."],"forward_implications":["The clustered form of Hajós' conjecture is settled up to a constant factor: $O(s)$ colors with bounded monochromatic components suffice for every $K_{s+1}$-subdivision-free graph.","In the bounded-treewidth case the number of colors is optimal: some treewidth-$(s-1)$ graphs need $s$ colors even with arbitrarily large allowed clustering, so Theorem 1 cannot be improved without extra assumptions.","Excluding a general minor instead of a subdivision costs exactly one extra color: every graph with no $H$-minor and no almost $(\\le 1)$-subdivision of $K_{s+1}$ is $(s+1)$-colorable with bounded clustering.","For subdivision exclusion, the color count grows linearly with the maximum degree $d$ of the excluded graph: $\\max\\{s+3d-5,2\\}$ colors suffice, and replacing the almost-subdivision prohibition by a $K_{s,t}$-subgraph prohibition gives $\\max\\{s+3d-4,2\\}$.","The lower-bound construction shows the clustering number cannot be independent of $s$; it must grow at least like $\\Omega(s/\\log s)$ in the worst case."],"supporting_citations":[{"why":"supplies the construction of graphs with no $K_{s+1}$-subdivision and chromatic number quadratic in $s$ over $\\log s$, motivating the clustered relaxation.","marker":"[8]"},{"why":"provides the structure theorem (Theorem 14) saying a graph excluding a bounded-degree subdivision either has a bounded exceptional set or low-order separations around every remaining vertex; this is the pivot in the proof of the main coloring lemma.","marker":"[22]"},{"why":"gives the companion list-coloring theorems and lemmas that produce bounded-clustering colorings from list assignments in graphs with no $K_{s,t}$ subgraph.","marker":"[23]"},{"why":"gives the companion lemma bounding the number of vertices with large common neighborhood, used to size the exceptional set $Z$.","marker":"[24]"},{"why":"presents the counterexamples that disproved Hajós' original conjecture, making the clustered weakening the natural claim to prove.","marker":"[3]"}],"fun_headline_variants":["Clustered Hajós: 4s−5 colors with bounded components","Bounded clusters give linear colors for Hajós variants","First O(s) bound for clustered Hajós conjecture","Clustered coloring: O(s) colors for subdivision-free graphs","Hajós conjecture's cluster version: linear colors suffice"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument's load-bearing premise is that graphs excluding a fixed bounded-degree subdivision admit the tangle-based small-exception structure described in Theorem 14, together with an unproved companion lemma (Lemma 19); if either of those gives way, the linear bound no longer follows.","fun_headline_variants_meta":{"raw":{"variants":["Clustered Hajós: 4s−5 colors with bounded components","Bounded clusters give linear colors for Hajós variants","First O(s) bound for clustered Hajós conjecture","Clustered coloring: O(s) colors for subdivision-free graphs","Hajós conjecture's cluster version: linear colors suffice"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000389,"raw_usage":{"total_tokens":2189,"prompt_tokens":1225,"completion_tokens":964,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":841,"completion_tokens_details":{"reasoning_tokens":879}},"tokens_in":841,"tokens_out":964,"duration_ms":9154,"temperature":1.0,"reasoning_tokens":879,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:27:21.479691+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For some fixed $s$ and arbitrarily large $\\eta$, construct a graph $G$ with no $K_{s+1}$-subdivision such that every coloring with at most $4s-5$ colors has a monochromatic component with more than $\\eta$ vertices; such a graph would directly disprove Theorem 6, the paper's central claim.","supporting_citations":[{"cited_title":"On the conjecture of Hajós.Combina- torica, 1(2):141–143, 1981","cited_arxiv_id":null,"evidence_quote":"supplies the construction of graphs with no $K_{s+1}$-subdivision and chromatic number quadratic in $s$ over $\\log s$, motivating the clustered relaxation."},{"cited_title":"Excludingsubdivisionsofboundeddegree graphs","cited_arxiv_id":null,"evidence_quote":"provides the structure theorem (Theorem 14) saying a graph excluding a bounded-degree subdivision either has a bounded exceptional set or low-order separations around every remaining vertex; this is the pivot in the proof of the main coloring lemma."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"presents the counterexamples that disproved Hajós' original conjecture, making the clustered weakening the natural claim to prove."}],"review_version":1}