{"id":"2de66e5b-d3f5-42ca-823a-14e31fd812c6","arxiv_id":"2506.01070","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For every tree T, almost all T-free graphs satisfy chi=omega, and for every cycle C_k except C_6, almost all C_k-free graphs satisfy chi=omega; C_6-free graphs are asymptotically chi-bounded with f(w)=(1+o(1))w^2/log w.","lead":"This paper studies which hereditary graph families are asymptotically chi-bounded, meaning almost every graph in the family can be colored with few colors relative to its clique number. It proves that for every tree and for every cycle except the 6-cycle, almost all graphs avoiding that induced subgraph are perfect, and gives a near-quadratic coloring bound for the exceptional 6-cycle case.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Central theorems depend on unverified structural classifications from two unpublished companion papers [23,24]; Theorem 9 (RS) for C6-free graphs has no reference or proof.","rationale":"We agree with the reader's assessment. The local framework (Theorem 11 and its proof) is sound: checking the Hall's theorem argument in detail, the dichotomy is exhaustive because if the Hall violator S has size < d then vertices in S have degree < d, and if |S| ≥ d but the complementary set B has size < d then vertices in B have degree < d; otherwise S and B are large sets with no edges. Thus Theorem 11 holds. The real weakness is external: the heavy structural results are not in the paper. Theorems 2 and 3 depend on seven unpublished tree classifications and three unpublished cycle classifications; Theorem 4 depends on an unreferenced assertion (Theorem 9 RS). These are not minor technical lemmas but the core content of the structural analysis. Without them, the paper is a framework plus examples, not a proof of the claimed theorems. We therefore confirm the CONDITIONAL verdict: accept only if the companion papers are available and the quoted theorems are correct. We do not see an internal contradiction that would force rejection.","tokens_in":11264,"tokens_out":20374,"duration_ms":187724,"concrete_test":"Obtain the manuscripts [23] and [24] and verify each quoted structural theorem (the seven tree cases and the cycle cases for k≠6 used in Theorem 10) and the exact statement of Theorem 9 (RS). Specifically, check that the partitions described satisfy the (µ,l)-partitionable definition with the same parameters used in Section 4, and that Theorem 9 appears with a proof in some accessible source. If any of these cannot be verified, Theorems 2-4 do not follow from the submitted paper.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The main results (Theorems 2, 3, 4) follow from Corollary 12 applied to Theorem 10 and, for C6, from Theorem 9. However, Theorem 10 is not self-contained: its proof quotes seven structural classification theorems from Reed and Yuditsky [24] (listed as 'To be submitted') for trees, and cycle classifications from Reed [23] (also 'To be submitted'), without stating or proving them. The proof of Theorem 10 also assumes these classifications yield partitionings into P4-free parts with the minimum-degree condition of Lemma 13; any error or missing condition there breaks Theorems 2 and 3. For C6, Theorem 9 ('RS') asserts that almost every C6-free graph partitions into a stable set and the complement of a girth-five graph, but no reference or proof is given. Since Theorem 4's bound f(w)=(1+o(1))w^2/log w depends entirely on Theorem 9 plus Shearer's bound, the C6 result is unsupported as submitted. The paper's own framework (Theorem 11, Corollary 12) appears correct, but it cannot substitute for the missing structural input.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces the notion of asymptotic χ-boundedness for hereditary families and states three main results: Theorem 2 says that for every tree T, almost all T-free graphs satisfy χ(G)=ω(G); Theorem 3 says the same for every cycle C_k with k≠6; Theorem 4 says the C_6-free graphs are asymptotically χ-bounded with bounding function f(w)=(1+o(1))w^2/log w. The method is a framework based on witnessing partitions and (µ,l)-partitionable hereditary families: Theorem 11 and Corollary 12 convert 'nicely partitionable' families into families in which almost all members are f(ω)-colourable. Theorem 10 is then presented as supplying the needed partitionability for trees and cycles, and Theorem 9 supplies the C_6 partition. The proofs of Theorems 2 and 3 are meant to follow from Theorem 10 plus Corollary 12; Theorem 4 follows from Theorem 9 plus Observation 8 and Shearer's bound.","tokens_in":11558,"tokens_out":8543,"duration_ms":81351,"significance":"If fully established, Theorems 2 and 3 are striking: they assert that almost all graphs avoiding a fixed tree or a non-6 cycle are perfect, which is far stronger than asymptotic χ-boundedness. Theorem 4 would give the first asymptotic χ-boundedness result for C_6-free graphs with an explicit bound of order w^2/log w. The framework of Theorem 11 and Corollary 12 is original, self-contained in outline, and potentially reusable; Corollary 17 for string graphs is a nice additional application. The principal weakness is that the load-bearing structural inputs are not contained in this manuscript: the proof of Theorem 10 is a sequence of citations to the unpublished manuscripts [24] and [23], and Theorem 9 is asserted without proof or reference. As submitted, the central theorems cannot be independently verified.","major_comments":[{"comment":"The proof of Theorem 10 quotes seven structural classification theorems from the unpublished manuscript [24] (Theorems 2.21, 2.22, 2.28, 2.33, 2.35, 2.37, 2.39) and analogous cycle classifications from the unpublished [23]. Since Theorem 10 is the entire structural input for Theorems 2 and 3, both main theorems are conditional on two manuscripts that are not available to the reader. The authors should either reproduce the statements (and proofs or precise public references) of these classifications, or clearly mark Theorems 2 and 3 as conditional on forthcoming work.","section":"§4, Proof of Theorem 10"},{"comment":"Lemma 13 is cited from [24] and is used in the proof of Theorem 10 to pass from the quoted structural partition results to the counting condition (b) in the definition of (µ,l)-partitionability. This is a second load-bearing dependence on [24], and the lemma is not stated in sufficient detail for the reader to verify the Θ(1) count. The dependence should be removed or the lemma proved in the manuscript.","section":"§4, Lemma 13"},{"comment":"Theorem 9, which asserts that almost every C_6-free graph can be partitioned into a stable set and the complement of a graph of girth five, is stated with the label '(RS)' but is given neither a proof nor a reference. Theorem 4 and the remark following it rest entirely on this statement together with Shearer's bound. As submitted, the C_6 result is unsupported.","section":"§3, Theorem 9 (RS)"},{"comment":"The case split in the proof of the two-part case is not justified. The sentence 'this lower bound on the degree also implies c−|S| ≥ c/(2b^2+1)' does not follow from the assumption that all vertices have degree greater than c/(2b^2+1); a Hall-violating set S can be large while |N(S)| is much smaller than |S|. The proof should be rewritten, for example by taking a minimal Hall violator and carefully relating the size of S to the degree condition, or by using a different concentration argument.","section":"§5, Proof of Theorem 11"}],"minor_comments":[{"comment":"The proof of Corollary 6 contains duplicated and garbled sentences: the two sentences beginning 'When we delete a stable set from C_{2k+1}' and 'When we delete a clique from C_{2k+1}' are repeated with the clauses swapped. The argument should be rewritten for clarity.","section":"§1, Corollary 6"},{"comment":"The phrase 'E_3-free' should be 'triangle-free' or defined explicitly; Shearer's theorem [29] is about the independence number of triangle-free graphs, and the notation E_3 is otherwise unused.","section":"§3, after Theorem 9"},{"comment":"The phrase 'an 1/9 -eqi-partition' is ungrammatical, and expressions such as 'partitioned into wpn(H)=α(T)−1 cliques' should be rephrased as 'partitioned into wpn(H)=α(T)−1 parts, each of which is a clique' or similar.","section":"§4, Proof of Theorem 10"},{"comment":"The proof refers to 'c0−1 variables' without defining c0; this should be 'c−1' or a defined symbol such as c_b.","section":"§5, Proof of Theorem 11"},{"comment":"The failure probability in Theorem 11 is written o_c(1); since c is the number of colours and may depend on n, the asymptotic should be clarified, for example as uniform in n over the range of c considered in Corollary 12.","section":"§5, Theorem 11"}],"recommendation":"major_revision","confidential_remarks":"The central theorems 2, 3, and 4 are conditional on two unpublished companion manuscripts [23,24] and on the unproved Theorem 9. I cannot certify the main results without access to those structural classifications. I recommend that the editor require the authors to make the companion papers available or to include the statements and proofs of the quoted theorems in the manuscript. The paper would also benefit from a careful proofreading pass, particularly around the proof of Theorem 11 and Corollary 6."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the quick take. The paper's own machinery—asymptotic chi-boundedness, witnessing partitions, and the probabilistic Theorem 11/Corollary 12 that turn partitions into colorings—is clean and looks correct. The proof of Theorem 11 is a standard but well-executed reduction to a random bipartite graph between color classes, with Hall and Chernoff doing the work. Corollary 12 is a genuinely reusable tool. If the structural inputs were in hand, the framework would indeed deliver Theorems 2 and 3 for all trees and all non-6 cycles.\n\nBut as submitted, those inputs are not in hand. The proof of Theorem 10 just quotes seven structural classification theorems from Reed-Yuditsky [24] and the cycle classifications from Reed [23], both 'To be submitted.' Theorem 9 (RS)—the C6 partition into a stable set and the complement of a girth-five graph—is asserted with no reference at all. So Theorems 2, 3, and 4 are, by the paper's own presentation, corollaries of results the reader cannot see. The stress-test note is right about this, and it is a load-bearing gap, not a stylistic quibble. If any of those classifications has a missing hypothesis (e.g. the minimum-degree condition in Lemma 13), the main theorems do not follow.\n\nCredit where due: the C6 application is a nice calculation—Shearer's bound gives cliques of size (1+o(1)) sqrt(l log l) in the complement of girth-five graphs, and the argument goes through modulo Theorem 9. The notion of asymptotic chi-boundedness is a natural and useful strengthening, and the paper is honest about what it is and is not proving. Minor blemishes: Observation 8 has a typo (sums f(ω(G)) instead of f_i(ω(G[V_i]))), and the proof of Corollary 6 has a garbled repeated sentence. These are cosmetic.\n\nWho gets value: people working on chi-boundedness or typical structure of H-free graphs will want to see this framework. But I would not cite the main theorems until [23] and [24] are available. The right call for an editor: send to referees, but tell the authors to post the companion papers or fold the structural proofs into an appendix. As it stands, it is a valuable framework paper riding on unverifiable foundations.","headline":"The framework is real and clean, but the headline theorems are only as solid as two unpublished companion papers and an unreferenced C6 assertion.","tokens_in":12017,"tokens_out":2642,"would_cite":false,"duration_ms":25186,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15","05C80"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that almost every graph avoiding a fixed tree or a cycle other than C6 has χ(G)=ω(G), and gives the first asymptotic χ-boundedness bound for C6-free graphs.","keywords":["asymptotic chi-boundedness","hereditary families","H-free graphs","chromatic number","clique number","witnessing partitions","C6-free graphs"],"falsifier":"Exhibit a fixed tree T (or a fixed cycle C_k with k≠6) and infinitely many n for which a non-negligible fraction of all T-free (or C_k-free) graphs on n vertices has χ(G)>ω(G), or, for C6, a non-negligible fraction of C6-free graphs on n vertices with χ(G) exceeding (1+o(1))ω(G)^2/log ω(G) or a violation of the asserted stable-set-complement-of-girth-five partition.","tokens_in":11039,"feed_emoji":"🎨","tokens_out":19369,"duration_ms":171311,"temperature":0.7,"pith_summary":"The paper studies hereditary families of graphs and asks what happens to the chromatic number of a typical member relative to its clique number. It proves two asymptotic statements: for every fixed tree T, almost all T-free graphs satisfy χ(G)=ω(G), and for every fixed cycle C_k with k≠6, almost all C_k-free graphs satisfy χ(G)=ω(G). The sole exception is C6, for which the paper establishes the first asymptotic χ-boundedness result with f(w)=(1+o(1))$w^{2}$/log w. These results say that typical members of these families are asymptotically perfect: their chromatic number equals their clique number, and the C5 case is shown to be genuinely perfect via the Strong Perfect Graph Theorem. The proof strategy turns typical structure into colourings through witnessing partitions and a probabilistic extension lemma.","feed_headline":"Almost all graphs avoiding a tree or non-6 cycle satisfy χ=ω","feed_subtitle":"Three theorems: near-perfect coloring for tree- and cycle-free graphs, plus a first asymptotic bound for the C6 case.","key_machinery":"The central objects are witnessing partitions and the witnessing partition number wpn(H): the largest t such that H cannot be partitioned into s stable sets and c cliques with s+c=t. A witnessing partition of H-freeness for G is a partition of V(G) into that many parts such that no way of partitioning H into s stable sets and c cliques is induced inside the parts. The conversion from partition to colouring is carried by the concept of a (b,f)-nicely partitionable hereditary family, meaning one in which almost every member admits one of finitely many certified patterns on a nearly equal partition, with each part either f(ω)-colourable using colour classes of size at most b or a clique, together with Corollary 12, which says such families are asymptotically f(ω)-colourable. The probabilistic heart is Theorem 11, which shows that given a partition with each part coloured in f(ω) colours using colour classes of bounded size, almost every extension of the pattern is f(ω)-colourable with slightly larger colour classes; its proof uses the standard matching condition for bipartite graphs and standard tail bounds for sums of independent Bernoulli variables.","core_discovery":"The central claim is that forbidding a fixed tree or a fixed cycle other than C6 pushes almost every graph in the family to the absolute minimum possible chromatic number: χ(G)=ω(G). The paper proves this not by bounding all H-free graphs but by describing the typical structure of almost all of them. For every such H, almost every H-free graph admits a nontrivial witnessing partition into a bounded number of parts, each of which induces a very restricted graph class (cliques, complements of matchings, graphs whose complements have only star or triangle components, and so on). The paper then proves a probabilistic lemma: if each part of such a partition has been coloured with the right number of colours using bounded colour-class sizes, then almost every way of adding the cross-part edges preserves that colouring. Applied to the witnessing partitions, this yields almost sure χ=ω. For C6 the partition is different, since almost every C6-free graph splits into a stable set and the complement of a graph of girth five, and a known bound on the clique number of such complements converts this into the stated f(w).","pith_inferences":["An asymptotic version of the classical conjecture for all forests would not follow from Theorem 2 by a simple subset argument: the 'almost all' quantifier does not automatically transfer from the larger tree-free family to the smaller forest-free subfamily, so a separate structural analysis of typical forest-free graphs would be needed.","The C6 analysis identifies a concrete bottleneck for improving Theorem 4: if the typical clique number of an n-vertex complement of a girth-five graph is asymptotically sqrt(n log n), then the squared bound is essentially forced, so measuring this quantity directly would determine whether the bound is tight.","The probabilistic extension lemma (Theorem 11) is a reusable black box: any hereditary family whose almost-all members can be certified by witnessing partitions with bounded-colour-class colourings will inherit an asymptotic χ-boundedness bound, as the string-graph corollary already demonstrates.","The main theorems are conditional on unpublished structural classifications; completing those classifications is the natural next step, and the same partitions should also yield enumeration results for tree-free and cycle-free graphs."],"forward_implications":["For every fixed tree T, almost every T-free graph can be coloured with exactly ω(G) colours, so the typical member of every tree-forbidding hereditary class satisfies the minimal possible colouring bound.","For every fixed cycle C_k with k≠6, almost every C_k-free graph satisfies χ(G)=ω(G), extending the previously known C4 and C5 cases to all other cycles and leaving C6 as the only cycle whose asymptotic behaviour is genuinely different.","The C6-free graphs are asymptotically χ-bounded with f(w)=(1+o(1))w^2/log w; the paper observes that improving this would require proving that complements of girth-five graphs typically have clique number of order sqrt(n log n).","The same partition-to-colouring framework yields that almost every string graph satisfies χ(G)=ω(G).","For every graph H that is critical in the sense that almost all H-free graphs are partitionable into s stable sets and c cliques for some fixed pair (s,c), almost every H-free graph satisfies χ(G)=ω(G)."],"supporting_citations":[{"why":"Supplies the seven structural classifications of almost all T-free graphs on which Theorem 10 is built.","marker":"[24]"},{"why":"Supplies the analogous classifications of almost all C_k-free graphs for cycles, invoked for Theorems 3 and 10.","marker":"[23]"},{"why":"Introduced the partition-to-colouring approach and proved the C4 and C5 cases that Theorems 2 and 3 extend.","marker":"[22]"},{"why":"The Strong Perfect Graph Theorem, used to conclude that graphs with the C5 witnessing partitions are perfect.","marker":"[7]"},{"why":"Defines the critical graphs and supplies the theorem on their obstruction subfamilies used in Corollary 18.","marker":"[1]"},{"why":"Provides the clique-number estimate for complements of girth-five graphs that gives the C6 bounding function.","marker":"[29]"},{"why":"Shows almost every string graph has a certifying partition, used to derive the string-graph corollary.","marker":"[18]"}],"fun_headline_variants":["For trees and cycles except C6, almost all H-free graphs satisfy χ=ω","Almost all H-free graphs for trees and non-6 cycles achieve χ=ω","C6-free graphs: asymptotic χ-bound of order w²/log w","New proof: typical H-free graphs for trees and cycles (minus C6) are ω-colourable"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the structural classifications of almost all T-free and C_k-free graphs quoted from two companion papers still listed as to be submitted, together with the unreferenced assertion that almost every C6-free graph can be partitioned into a stable set and the complement of a girth-five graph, are all correct; if any of these fails, the corresponding theorem does not follow.","fun_headline_variants_meta":{"raw":{"variants":["For trees and cycles except C6, almost all H-free graphs satisfy χ=ω","Almost all H-free graphs for trees and non-6 cycles achieve χ=ω","C6-free graphs: asymptotic χ-bound of order w²/log w","New proof: typical H-free graphs for trees and cycles (minus C6) are ω-colourable"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000468,"raw_usage":{"total_tokens":2328,"prompt_tokens":935,"completion_tokens":1393,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":551,"completion_tokens_details":{"reasoning_tokens":1303}},"tokens_in":551,"tokens_out":1393,"duration_ms":13745,"temperature":1.0,"reasoning_tokens":1303,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T11:53:40.641295+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit a fixed tree T (or a fixed cycle C_k with k≠6) and infinitely many n for which a non-negligible fraction of all T-free (or C_k-free) graphs on n vertices has χ(G)>ω(G), or, for C6, a non-negligible fraction of C6-free graphs on n vertices with χ(G) exceeding (1+o(1))ω(G)^2/log ω(G) or a violation of the asserted stable-set-complement-of-girth-five partition.","supporting_citations":[{"cited_title":"Reed and Y","cited_arxiv_id":null,"evidence_quote":"Supplies the seven structural classifications of almost all T-free graphs on which Theorem 10 is built."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the analogous classifications of almost all C_k-free graphs for cycles, invoked for Theorems 3 and 10."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduced the partition-to-colouring approach and proved the C4 and C5 cases that Theorems 2 and 3 extend."},{"cited_title":"Chudnovsky, N","cited_arxiv_id":null,"evidence_quote":"The Strong Perfect Graph Theorem, used to conclude that graphs with the C5 witnessing partitions are perfect."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the clique-number estimate for complements of girth-five graphs that gives the C6 bounding function."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Shows almost every string graph has a certifying partition, used to derive the string-graph corollary."}],"review_version":1}