{"id":"bdaa46bb-f298-4c9f-876b-0eaecc430573","arxiv_id":"2608.13519","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Every fork-free graph is perfectly weight divisible, confirming Sivaraman's conjecture and yielding chi(G) at most binomial(omega(G)+1,2) for every fork-free graph.","lead":"This paper proves that every fork-free graph can be split into one perfect part and one part with smaller clique number, even when the vertices carry positive weights. The result settles Sivaraman's conjecture and yields a quadratic upper bound on the chromatic number of fork-free graphs.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Main theorem depends on the unpublished Xu–Zhuang reduction (Theorem 2.1) that minimal non-PWD fork-free graphs are claw-free; no proof is supplied, and the entire fork-free case reduces to this black box.","rationale":"I read the proof as a reduction to the claw-free case followed by a long structural proof. The internal argument from Lemma 2.3 through Theorem 6.3 is coherent; I could not identify a gap in Lemma 2.4 or in the composition argument. There are minor typos (e.g., Lemma 4.4 says G[MG(x)] is bipartite when the complement is bipartite; Section 8 writes G=H where the complement is intended), but these do not affect the central theorem. The decisive risk is Theorem 2.1. The paper's own Section 7 shows that if every minimal non-PWD fork-free graph is claw-free, then Theorem 1.4 follows; it does not otherwise use fork-freeness. Because [30] is an arXiv preprint and the proof is not included, correctness of the paper hinges on an unverified external result. This is not an internal inconsistency, but it is a load-bearing verification gap. I agree with the reader's identification. My recommendation is to keep the CONDITIONAL verdict: accept only if the Xu–Zhuang proof is verified or included; otherwise the theorem is not fully established.","tokens_in":24794,"tokens_out":35557,"duration_ms":326697,"concrete_test":"Obtain the full proof of Theorem 2.1 from the authors of [30] and re-derive the key reduction: from a minimal non-PWD fork-free graph G that contains an induced claw with center c, construct a proper induced subgraph G' and a positive integral weight function witnessing that G' is not PWD, contradicting minimality. Verify every case of the claw-center configuration against the same weighted definition used in this paper, and confirm that the argument does not rely on Theorem 1.4 or on the claw-free structure theorem. If the reduction cannot be reproduced, the verdict should remain conditional on inclusion of that proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 1.4 is exactly: choose a minimal fork-free counterexample; invoke Theorem 2.1 (Xu–Zhuang [30]) to conclude it is claw-free; then apply Theorem 7.1. Theorem 2.1 is therefore the only place where the fork-free hypothesis is used. The paper states it as a quoted theorem and gives no proof, no proof sketch, and no independent verification. If that reduction is false or has a gap for the weighted definition used here (positive integral weights, every induced subgraph), the argument establishes only the claw-free case, not Conjecture 1.3. The rest of the proof (Sections 3–7) is an elaborate and largely self-contained proof of the claw-free case, so the vulnerability is localized but decisive. Also load-bearing, though secondary, is the assertion that every two-marker member of Z0 lies in Z1,...,Z5 (Section 3.2) and the use of the full Chudnovsky–Seymour structure theorem; neither is reproduced, but both are standard. The unpublished status of [30] is the single greatest correctness risk.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript proves that every fork-free graph is perfectly weight divisible (Theorem 1.4), thereby confirming Sivaraman's conjecture that every fork-free graph is perfectly divisible and yielding the quadratic chi-binding function chi(G) <= binom(omega(G)+1,2) (Corollary 1.5). The proof strategy is: (i) invoke Theorem 2.1 of Xu and Zhuang [30] to reduce the fork-free case to the claim that every minimal non-perfectly weight divisible fork-free graph is claw-free; (ii) prove that every claw-free graph is perfectly weight divisible (Theorem 7.1). The claw-free proof takes a minimal counterexample, derives structural restrictions (no simplicial vertex, no clique cutset), applies the Chudnovsky-Seymour global structure theorem, and then builds perfect Omega-transversals in every outcome: vertex sets covered by three cliques, thickenings of S1, S3, S7, and compositions over a multigraph with two-marker stripe pieces of types Z1-Z5. Weights are handled by replacing each vertex with a clique of its weight. The paper is largely self-contained after the external structure theorems, and the blow-up and composition arguments are worked out in detail.","tokens_in":24957,"tokens_out":24430,"duration_ms":232709,"significance":"If the result is correct, it is a substantial advance: it resolves Sivaraman's conjecture and proves a stronger weighted statement, and it improves the known chi-binding function for fork-free graphs from 7*omega(G)^2 to the quadratic binomial bound. The paper gives explicit, detailed proofs for the claw-free case, including the minimal-counterexample lemmas, the transversal constructions for the three basic thickening classes, and the orientation/composition argument. The main correctness risk is that the fork-free reduction is outsourced to an unpublished preprint, and one proof in Section 4 contains an apparent misstatement; both issues are localized and potentially repairable.","major_comments":[{"comment":"The proof of Theorem 1.4 uses Theorem 2.1 as the only place where the fork-free hypothesis enters: the minimal fork-free counterexample is declared claw-free by Xu and Zhuang [30], and then Theorem 7.1 applies. Since [30] is an unpublished arXiv preprint (2504.14863v3) and the weighted definition used here (positive integral weights, every induced subgraph) is exactly the setting of the reduction, the manuscript should either reproduce a proof of Theorem 2.1 or give a detailed verification that the stated reduction covers the present definition, ideally with the preprint's publication status. As it stands, the central fork-free claim rests entirely on this black box.","section":"Section 2, Theorem 2.1"},{"comment":"The proof of Lemma 4.4 states that every bag retained in M_G(x) is an independent set in G[M_G(x)] and concludes that G[M_G(x)] is bipartite. This is not correct as written: in a thickening each bag X_s is a strong clique, hence a clique in G, so retained bags are cliques rather than independent sets; for instance, in a thickening of an antiprismatic C5 with non-singleton bags, M_G(x) is the join of the two retained bags and is a complete graph, not bipartite. The intended argument is presumably that the complement of G[M_G(x)] is bipartite with parts indexed by the bipartition of Q, so G[M_G(x)] is co-bipartite and therefore perfect. Since Lemma 4.4 is used in Theorem 7.1 for the S7 case, this proof must be corrected.","section":"Section 4, Lemma 4.4"},{"comment":"The assertion that every two-marker member of Z0 belongs to Z1,...,Z5 is used in Theorem 3.2(iii) to restrict all non-spot pieces in the composition outcome to types Z1-Z5. The accompanying marker-counting remark shows only that, among the listed classes Z1-Z15, the two-marker classes are Z1-Z4 and possibly Z5; it does not by itself exclude two-marker members of Z0 arising from other sources in the definition of Z0. Please provide a precise citation to the relevant statement in [8] or a short proof of this classification, because the transversal constructions in Section 5 are built specifically for Z1-Z5 and the composition argument depends on this restriction.","section":"Section 3.1, Z0 classification sentence"}],"minor_comments":[{"comment":"The construction as written sets G = H and then claims alpha(G) = omega(H) <= 3; this equality is false for G = H. The intended graph must be the complement of H, for which alpha(G) = omega(H) <= 3 and omega(G) = alpha(H) < k. Please correct the sentence 'Let G = H' accordingly.","section":"Section 8, Proposition 8.3(i)"},{"comment":"There are numerous missing spaces in the LaTeX-rendered text (e.g., 'graphG', 'A graphG isperfectly'), and several displayed formulas are not fully separated from the surrounding prose; these should be cleaned up in the final version.","section":"Various"},{"comment":"The phrase 'a independent set' should be 'an independent set', and the direct check for the Mycielski-Groetzsch graph would be easier to verify if the three branch-vertex cases were spelled out in a table rather than in a single sentence.","section":"Section 8, Proposition 8.3(ii)-(iii)"}],"recommendation":"major_revision","confidential_remarks":"The decisive issue is the dependence on the unpublished reduction theorem [30]. If the authors can include a proof or confirm that the theorem has been accepted in a refereed venue, and if Lemma 4.4 is corrected, I would view the main theorem as credible and significant. The Section 8 typo in Proposition 8.3(i) suggests the sharpness discussion needs a careful proofread. There is no circularity concern: the external dependencies are cited and not self-referential."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe one thing to know: this paper claims to settle Sivaraman's conjecture that every fork-free graph is perfectly divisible, and it actually proves the stronger statement that every fork-free graph is perfectly weight divisible, giving chi <= C(omega+1,2). The machinery is a serious piece of work. Sections 3 through 7 develop a transversal-based proof that every claw-free graph is perfectly weight divisible, using the Chudnovsky–Seymour global structure theorem. That part is detailed, coherent, and largely self-contained; the lemmas for the stripe classes and the composition argument are carefully done, and the line-graph cut lemma in Section 6 is a nice combinatorial tool. If the reduction to claw-free is valid, this is a genuine advance.\n\nThe soft spot is exactly that reduction. Theorem 1.4 is proven by taking a minimal fork-free counterexample and invoking Theorem 2.1 from a Xu–Zhuang preprint [30], which asserts that such a counterexample must be claw-free. The paper gives no proof and no sketch of that theorem, and it is load-bearing in the strongest sense: it is the only place where the fork-free hypothesis is used. If that result has a gap, Theorem 1.4 collapses to the claw-free theorem. That is a real fragility, but it is a verification problem rather than an internal contradiction. The core argument does not appear circular, and there are no fitted parameters or invented entities.\n\nThe secondary dependencies are standard and less concerning: the Chudnovsky–Seymour theorem is used as a black box, and the assertion that every two-marker member of Z0 lies in Z1..Z5 is stated without proof. Both are credible to experts. There are also minor editorial issues, including a few typos in Section 8 and in Lemma 2.4. None of this undermines the main line.\n\nWho should read this? Anyone working on chi-boundedness or perfect divisibility. It is exactly the kind of result that deserves a serious referee, not a desk reject. The referee's main job is to check whether [30] really does imply the reduction for this weighted definition, and to verify the composition argument. My recommendation: send it to review, and ask the authors to either include a proof of Theorem 2.1 or make the dependence on the preprint fully explicit and public.","headline":"Resolves Sivaraman's conjecture with a strong weighted theorem, but the fork-free case hangs on an unpublished reduction theorem that is quoted, not proved.","tokens_in":25522,"tokens_out":1859,"would_cite":true,"duration_ms":18703,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15","05C75"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every fork-free graph is perfectly weight divisible, and the chromatic number of any fork-free graph is at most $\\binom{\\omega(G)+1}{2}$.","keywords":["fork-free graphs","perfect weight divisibility","perfect divisibility","claw-free graphs","perfect transversals","chromatic number","chi-boundedness","graph coloring"],"falsifier":"Exhibit a fork-free graph $G$, positive integer weights, and an induced subgraph $H$ with at least one edge such that every partition $V(H)=A\\cup B$ either has $H[A]$ imperfect or still contains a maximum-weight clique in $H[B]$. A more targeted check is to look for a minimal non-perfectly weight divisible fork-free graph that contains an induced claw; such a graph would contradict the quoted reduction and hence the main theorem.","tokens_in":24561,"feed_emoji":"🎨","tokens_out":16515,"duration_ms":137723,"temperature":0.7,"pith_summary":"This paper proves that every fork-free graph is perfectly weight divisible; a fork is a three-leaf star with one edge subdivided once. In plain terms, once the vertices of any induced subgraph with at least one edge are given positive integer weights, the vertex set can be split into two parts: one part induces a perfect graph, and the other part has maximum weighted clique strictly below that of the original subgraph. Because a perfect graph can be colored with exactly as many colors as its largest clique, this split yields by induction the bound $\\chi(G)\\le \\binom{\\omega(G)+1}{2}$ for every fork-free graph $G$, settling the conjecture that fork-free graphs are perfectly divisible. The proof achieves this by first showing the stronger statement that every claw-free graph is perfectly weight divisible, using the global structure theory of claw-free graphs to build a set that meets every maximum clique while inducing a perfect graph. Reading the argument charitably, the fork-free case is inherited from the claw-free case through a reduction theorem quoted from another preprint.","feed_headline":"Every fork-free graph is perfectly weight divisible","feed_subtitle":"The weighted split gives a quadratic upper bound on the chromatic number of every fork-free graph.","key_machinery":"The load-bearing object is a perfect $\\Omega$-transversal: a subset $S$ of vertices that meets every maximum clique of the weighted, blown-up graph and induces a perfect graph. Observation 2.2 turns the existence of such a transversal into the existence of a weighted perfect division, so the entire proof reduces to finding transversals. The structural engine is the global structure theorem for claw-free graphs, which, for a connected claw-free graph with no simplicial vertex and no clique cutset, leaves only three possibilities: the vertex set is covered by three cliques; the graph is a thickening of one of the basic classes (icosahedral, long circular interval, antiprismatic); or the graph is a composition over a loopless multigraph whose non-spot pieces are the five two-marker stripe types $Z_1,\\dots,Z_5$. Each case is handled by an explicit perfect set: deleting a vertex whose neighborhood misses a maximum clique, anti-neighborhoods that are perfect, explicit independent unions of bags for the icosahedral class, and oriented terminal sets glued piece by piece in the composition case.","core_discovery":"The paper's central claim, Theorem 1.4, is that every fork-free graph is perfectly weight divisible: for every positive integral weight function $h$ and every induced subgraph $H$ with at least one edge, there is a partition $V(H)=A\\sqcup B$ with $H[A]$ perfect and $\\omega_h(H[B])<\\omega_h(H)$. Since the unweighted case ($h\\equiv 1$) is exactly perfect divisibility, this resolves the open conjecture for fork-free graphs. The proof's intermediate theorem is that every claw-free graph is perfectly weight divisible. A minimal counterexample is shown to be connected, free of simplicial vertices and clique cutsets, and after blowing up each weighted vertex into a clique of size $h(v)$, it falls into one of the cases of the claw-free structure theorem; in every case a perfect transversal exists, giving the contradiction. Corollary 1.5, $\\chi(G)\\le\\binom{\\omega(G)+1}{2}$, follows immediately by induction on the clique number.","pith_inferences":["This reader infers that the transversal method is a reusable template: any hereditary class whose minimal counterexamples have no simplicial vertex and no clique cutset, and whose structure theorem yields explicit perfect transversals, should be perfectly weight divisible by the same argument.","The fork-free statement is only as wide as the quoted reduction from another preprint that minimal counterexamples are claw-free; checking that reduction independently is the natural next step before relying on the full fork-free conclusion.","The paper's closing question about the tree $E=S_{1,2,2}$ is a plausible next target: since the proof already handles claw-free graphs, any structure theory for $E$-free graphs that produced the same perfect transversal cases would directly give the conjectured perfect divisibility."],"forward_implications":["Every fork-free graph has a perfect division, so the open conjecture on perfect divisibility of fork-free graphs is settled.","The chromatic number of every fork-free graph is at most $\\binom{\\omega(G)+1}{2}$, improving the previous general quadratic bound $\\chi(G)\\le 7\\omega(G)^2$.","Because the divisibility property is hereditary, the same partition argument applies to every induced subgraph of a fork-free graph, so the bound is stable under taking induced subgraphs.","The intermediate theorem supplies the stronger weighted statement for the entire claw-free class, and the fork-free class inherits perfect weight divisibility rather than only unweighted divisibility."],"supporting_citations":[{"why":"Supplies the reduction that a minimal non-perfectly weight divisible fork-free graph must be claw-free; the fork-free theorem inherits the claw-free proof through this result.","marker":"[30]"},{"why":"Global structure theorem for claw-free graphs; yields the three-outcome decomposition (three cliques, basic thickenings, or composition) that the proof splits into cases.","marker":"[8]"},{"why":"Strong perfect graph theorem; used to certify perfection and to force minimal counterexamples to contain odd holes or odd antiholes.","marker":"[6]"},{"why":"Proves that every graph obtained by thickening a linear interval trigraph is perfect; needed for stripe type Z1 and for long circular interval graphs.","marker":"[5]"},{"why":"Substitution theorem for perfect graphs; used to show clique blow-ups and the icosahedral transversal sets are perfect.","marker":"[22]"},{"why":"Line-coloring theorem for bipartite multigraphs; used to prove the selected cut's line graph is perfect in the spot-edge part of compositions.","marker":"[23]"}],"fun_headline_variants":["Fork-free graphs are perfectly weight divisible","Sivaraman conjecture proven for fork-free graphs","Every fork-free graph admits a perfect weight split","Weighted perfect divisibility holds for all fork-free graphs","Fork-free graphs: perfect divisibility weighted"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the quoted reduction, asserted from another preprint without proof, that every minimal non-perfectly weight divisible fork-free graph is claw-free; if that reduction fails, the argument proves the claw-free case but not the fork-free case.","fun_headline_variants_meta":{"raw":{"variants":["Fork-free graphs are perfectly weight divisible","Sivaraman conjecture proven for fork-free graphs","Every fork-free graph admits a perfect weight split","Weighted perfect divisibility holds for all fork-free graphs","Fork-free graphs: perfect divisibility weighted"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000235,"raw_usage":{"total_tokens":1479,"prompt_tokens":905,"completion_tokens":574,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":521,"completion_tokens_details":{"reasoning_tokens":502}},"tokens_in":521,"tokens_out":574,"duration_ms":5535,"temperature":1.0,"reasoning_tokens":502,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T05:13:17.194581+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit a fork-free graph $G$, positive integer weights, and an induced subgraph $H$ with at least one edge such that every partition $V(H)=A\\cup B$ either has $H[A]$ imperfect or still contains a maximum-weight clique in $H[B]$. A more targeted check is to look for a minimal non-perfectly weight divisible fork-free graph that contains an induced claw; such a graph would contradict the quoted reduction and hence the main theorem.","supporting_citations":[{"cited_title":"On minimal nonperfectly divisible fork-free graphs","cited_arxiv_id":"2504.14863","evidence_quote":"Supplies the reduction that a minimal non-perfectly weight divisible fork-free graph must be claw-free; the fork-free theorem inherits the claw-free proof through this result."},{"cited_title":"Chudnovsky and P","cited_arxiv_id":null,"evidence_quote":"Global structure theorem for claw-free graphs; yields the three-outcome decomposition (three cliques, basic thickenings, or composition) that the proof splits into cases."},{"cited_title":"Chudnovsky, N","cited_arxiv_id":null,"evidence_quote":"Strong perfect graph theorem; used to certify perfection and to force minimal counterexamples to contain odd holes or odd antiholes."},{"cited_title":"Chudnovsky and M","cited_arxiv_id":null,"evidence_quote":"Proves that every graph obtained by thickening a linear interval trigraph is perfect; needed for stripe type Z1 and for long circular interval graphs."},{"cited_title":"Lovász, Normal hypergraphs and the perfect graph conjecture,Discrete Math.2(1972), 253–267","cited_arxiv_id":null,"evidence_quote":"Substitution theorem for perfect graphs; used to show clique blow-ups and the icosahedral transversal sets are perfect."},{"cited_title":"Lovász and M","cited_arxiv_id":null,"evidence_quote":"Line-coloring theorem for bipartite multigraphs; used to prove the selected cut's line graph is perfect in the spot-edge part of compositions."}],"review_version":1}