Pith. sign in

REVIEW 3 major objections 3 minor 30 references

Every fork-free graph is perfectly weight divisible

T0 review · 3 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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}$.

desk verdict 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. read the letter →

arxiv 2608.13519 v1 pith:52WI56LZ submitted 2026-08-13 math.CO

Feng Liu , Shuang Sun , Yan Wang , Qi Wu , Jiasheng Zeng This is my paper · ORCID
classification math.CO MSC 05C1505C75
keywords fork-freegraphsperfectweightdivisibilityclaw-freetransversalschromaticnumberchi-boundednessgraphcoloring
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

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.

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 (3)
  1. [Section 2, Theorem 2.1] 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.
  2. [Section 4, Lemma 4.4] 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.
  3. [Section 3.1, Z0 classification sentence] 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.
minor comments (3)
  1. [Section 8, Proposition 8.3(i)] 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.
  2. [Various] 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.
  3. [Section 8, Proposition 8.3(ii)-(iii)] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the fork-free theorem is reduced to an external theorem and then proved via external structure theory.

full rationale

No circularity found. The central claim (Theorem 1.4) is obtained by invoking the external reduction Theorem 2.1 (Xu–Zhuang [30]) to pass from fork-free minimal counterexamples to claw-free graphs, and then proving Theorem 7.1, that every claw-free graph is perfectly weight divisible, from the Chudnovsky–Seymour global structure theorem. Each reduction is a genuine mathematical implication rather than a definitional identity: Observation 2.2 recasts h-perfect division as a transversal condition, but both directions are proved from the definition of maximum-weight cliques; the blow-up argument in Theorem 7.1 converts weights to clique sizes and is not assumed. No fitted parameters are introduced, and no quantity is predicted from data to which it was fitted. The only notable reliance is the external Xu–Zhuang reduction, an unpublished arXiv preprint; that is a verification and completeness risk, not a circularity, because the paper neither defines that theorem in terms of its own conclusion nor derives it from the theorem being proved. Self-citations such as [20] and [21] are historical background only and carry no load in the proof. Accordingly the circularity score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The proof rests on established structural theorems in graph theory and on one very recent external reduction. There are no fitted constants and no invented objects. The key unproved input is the Xu-Zhuang theorem that reduces fork-free counterexamples to claw-free ones.

assumptions (5)
  • standard math Strong Perfect Graph Theorem: a graph is perfect iff it contains no odd hole and no odd antihole.
    Invoked in Lemma 2.4 to infer that a non-perfect induced subgraph contains an odd hole or an odd antihole.
  • standard math Chudnovsky-Seymour structure theorem for claw-free trigraphs: a connected claw-free trigraph whose vertex set is not covered by three cliques is either a thickening of S1 union S3 union S7 or has an optimal nontrivial purified strip-structure.
    Backbone of Theorem 3.2; all cases of the main proof are channeled through this classification.
  • domain assumption Xu-Zhuang reduction: every minimal non-perfectly weight divisible fork-free graph is claw-free.
    Load-bearing reduction used in Theorem 7.1; not proved in this paper and stated from a recent arXiv preprint.
  • standard math Lovasz substitution theorem: every clique blow-up of a perfect graph is perfect.
    Used in Lemma 4.5 for thickenings of icosahedral trigraphs.
  • standard math Ko nig line-coloring theorem: the chromatic number of the line graph of a bipartite multigraph equals its maximum degree.
    Used in Lemma 6.1 to show perfectness of the selected cut in the line graph of a multigraph.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Every fork-free graph is perfectly weight divisible." pith.science (2026). https://pith.science/paper/52WI56LZ

@misc{pith2026260813519,
  author       = {Pith},
  title        = {Pith review of: Every fork-free graph is perfectly weight divisible},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/52WI56LZ}},
  note         = {Machine review of arXiv:2608.13519}
}
abstract

A graph $G$ is \emph{perfectly weight divisible} if, for every positive integral weight function on $V(G)$ and every induced subgraph $H$ of $G$ with at least one edge, the vertex set $V(H)$ can be partitioned into two sets $A$ and $B$ such that $H[A]$ is perfect and the maximum weight of a clique in $H[B]$ is smaller than the maximum weight of a clique in $H$. Perfect divisibility and its weighted form provide a natural approach to polynomial $\chi$-boundedness. A \emph{fork}, also known as a \emph{chair}, is the graph obtained from a claw by subdividing one of its edges once. In this paper, we prove that every fork-free graph is perfectly weight divisible. As a consequence, we confirm a conjecture of Sivaraman that every fork-free graph is perfectly divisible.

Figures

Figures reproduced from arXiv: 2608.13519 by the authors.

Figure 1
Figure 1. Illustrations of the configurations. Karthick, Kaufmann, and Sivaraman [17] proved Conjecture 1.3 for {fork, F}-free graphs when F ∈ {P6, co-dart, bull}. Wu and Xu [29] proved that every {fork, odd balloon}-free graph is perfectly divisible. As observed by Xu and Zhuang [30], their argument in fact proves perfect weight divisibility. Xu and Zhuang [30] also proved that every {fork, P7}-free graph and every {fork, P6… view at source ↗
Figure 2
Figure 2. A linear interval trigraph. Solid edges represent strong adjacencies, the dashed edge v1v3 represents a semiadjacency, and all unrepresented pairs are strongly antiadjacent. To connect these trigraphs with perfect graphs, we use the standard trigraph conventions of Chudnovsky and Seymour [8, Section 2]. Let k ≥ 4. A hole in a trigraph T is an ordering v1, . . . , vk of distinct vertices such that consecutive vertice… view at source ↗
Figure 3
Figure 3. A circular representation of a long circular interval trigraph. The four arcs are drawn at different distances from Σ for clarity. Their endpoint pairs are semiadjacent, while two vertices lying in no common arc are strongly antiadjacent. The following lemma gives the property of long circular interval trigraphs that we need. Lemma 4.3. Let G be a thickening of a long circular interval trigraph. Then G[MG(x)] is per… view at source ↗
Figures from the paper (8 more)
Figure 4
Figure 4. Figure 4: The icosahedral graph T1 = T0 − v11, which belongs to S1. Every displayed edge is a strong adjacency, and every unrepresented pair is strongly antiadjacent. We use the following consequence of the substitution theorem of Lovász [22]: Every clique blow-up of a perfect g…
Figure 5
Figure 5. Figure 5: A representative stripe of type Z1. The linear ordering in the definition gives the perfectness property needed later. Lemma 5.1. Let S be the piece of a thickening of a stripe of type Z1, and let A1, A2 be its terminals. Then both S − A1 and S − A2 are perfect. Proof.…
Figure 6
Figure 6. Figure 6: A representative stripe of type Z2 with n = 2. Although the adjacencies in Z2 are more involved, deleting either terminal leaves a graph covered by two cliques. Lemma 5.2. Let S be the piece of a thickening of a stripe of type Z2, and let A1, A2 be its terminals. Then …
Figure 7
Figure 7. Figure 7: A representative stripe of type Z3. The line-trigraph description again gives a simple structure after either terminal is removed. Lemma 5.3. Let S be the piece of a thickening of a stripe of type Z3, and let A1, A2 be its terminals. Then both S − A1 and S − A2 are per…
Figure 8
Figure 8. Figure 8: The stripe of type Z4. As in the preceding two types, deleting either terminal leaves a cobipartite graph. Lemma 5.4. Let S be the piece of a thickening of a stripe of type Z4, and let A1, A2 be its terminals. Then both S − A1 and S − A2 are perfect. Proof. Let (Xv : v…
Figure 9
Figure 9. Figure 9: shows a representative member in which v11 and v12 are absent and v9v10 is semiadjacent. v1 v2 v4 v3 v5 v6 v9 v10 v7 v8 marker marker [PITH_FULL_IMAGE:figures/full_fig_p016_9.png]
Figure 10
Figure 10. Figure 10: K1,4 S1,1,3 E = S1,2,2 S2,2,2 [PITH_FULL_IMAGE:figures/full_fig_p020_10.png]
Figure 11
Figure 11. Figure 11: The Mycielski–Grötzsch graph M. Lemma 8.2 (Hu–Xiong [15]). M is not perfectly divisible. Proposition 8.3. The following statements hold. (i) There is a K1,4-free graph that is not perfectly divisible. (ii) There is an S1,1,3-free graph that is not perfectly divisible.…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

30 extracted references · 27 canonical work pages

  1. [30]

    On minimal nonperfectly divisible fork-free graphs

    B. Xu and M. Zhuang, On minimal nonperfectly weight divisible fork-free graphs, arXiv:2504.14863v3, 2026. 23

    work page Pith review arXiv 2026

  2. [8]

    Chudnovsky and P

    M. Chudnovsky and P. Seymour, Claw-free graphs. V. Global structure,J. Combin. Theory Ser. B 98(2008), 1373–1410

    work page 2008

  3. [1]

    J. A. Bondy and U. S. R. Murty,Graph Theory, Graduate Texts in Mathematics, Vol. 244, Springer, London, 2008

    work page 2008

  4. [2]

    Brause, B

    C. Brause, B. Randerath, I. Schiermeyer, and E. Vumar, On the chromatic number of2K2-free graphs,Discrete Appl. Math.253(2019), 14–24

    work page 2019

  5. [3]

    Chudnovsky, L

    M. Chudnovsky, L. Cook, and P. Seymour, Excluding the fork and antifork,Discrete Math.343 (2020), Article No. 111786

    work page 2020

  6. [4]

    Chudnovsky, S

    M. Chudnovsky, S. Huang, T. Karthick, and J. Kaufmann, Square-free graphs with no induced fork,Electron. J. Combin.28(2021), Paper No. P2.20

    work page 2021

  7. [5]

    Chudnovsky and M

    M. Chudnovsky and M. Plumettaz, The structure of claw-free perfect graphs,J. Graph Theory75 (2014), 203–230

    work page 2014

  8. [6]

    Chudnovsky, N

    M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, The strong perfect graph theorem, Ann. of Math.164(2006), 51–229

    work page 2006

Show all 30 references
  1. [7]

    Chudnovsky and P

    M. Chudnovsky and P. Seymour, Claw-free graphs. IV. Decomposition theorem,J. Combin. Theory Ser. B98(2008), 839–938

    2008

  2. [9]

    Chudnovsky and P

    M. Chudnovsky and P. Seymour, Claw-free graphs. VI. Colouring,J. Combin. Theory Ser. B100 (2010), 560–572

    2010

  3. [10]

    Chudnovsky and V

    M. Chudnovsky and V. Sivaraman, Perfect divisibility and 2-divisibility,J. Graph Theory90 (2019), 54–60

    2019

  4. [11]

    Erdős, Graph theory and probability,Canad

    P. Erdős, Graph theory and probability,Canad. J. Math.11(1959), 34–38

    1959

  5. [12]

    Faudree, E

    R. Faudree, E. Flandrin, and Z. Ryjáček, Claw-free graphs: a survey,Discrete Math.164(1997), 87–147

    1997

  6. [13]

    Gyárfás, On Ramsey covering-numbers, inInfinite and Finite Sets, Vol

    A. Gyárfás, On Ramsey covering-numbers, inInfinite and Finite Sets, Vol. II, Colloq. Math. Soc. János Bolyai, Vol. 10, North-Holland, Amsterdam, 1975, 801–816

    1975

  7. [14]

    C. T. Hoàng, On the structure of (banner, odd hole)-free graphs,J. Graph Theory89(2018), 395–412

    2018

  8. [15]

    Hu and B

    H. Hu and B. Xiong, Perfect divisions in(P3∪P 4,P 6,bull)-free graphs,Mathematics13(2025), Article No. 3358

    2025

  9. [16]

    Q. Hu, B. Xu, and M. Zhuang, Some properties of minimally nonperfectly divisible graphs, arXiv:2603.01967v2, 2026

    2026

  10. [17]

    Karthick, J

    T. Karthick, J. Kaufmann, and V. Sivaraman, Coloring graph classes with no induced fork via perfect divisibility,Electron. J. Combin.29(2022), Paper No. P3.19

    2022

  11. [18]

    H. A. Kierstead and S. G. Penrice, Radius two trees specifyχ-bounded classes,J. Graph Theory 18(1994), 119–129

    1994

  12. [19]

    J. H. Kim, The Ramsey numberR(3,t)has order of magnitudet2/logt,Random Structures Algorithms7(1995), 173–207

    1995

  13. [20]

    K. Lan, F. Liu, D. Wu, and Y. Zhou, Trisimplicial vertices in(fork,odd parachute)-free graphs, Discrete Math.349(2026), Article No. 114920

    2026

  14. [21]

    X. Liu, J. Schroeder, Z. Wang, and X. Yu, Polynomialχ-binding functions fort-broom-free graphs, J. Combin. Theory Ser. B162(2023), 118–133

    2023

  15. [22]

    Lovász, Normal hypergraphs and the perfect graph conjecture,Discrete Math.2(1972), 253–267

    L. Lovász, Normal hypergraphs and the perfect graph conjecture,Discrete Math.2(1972), 253–267

    1972

  16. [23]

    Lovász and M

    L. Lovász and M. D. Plummer,Matching Theory, North-Holland Mathematics Studies, Vol. 121, North-Holland, Amsterdam, 1986

    1986

  17. [24]

    Mattheus and J

    S. Mattheus and J. Verstraëte, The asymptotics ofr(4,t),Ann. of Math.199(2024), 919–941

    2024

  18. [25]

    Schiermeyer and B

    I. Schiermeyer and B. Randerath, Polynomialχ-binding functions and forbidden induced subgraphs: a survey,Graphs Combin.35(2019), 1–31. 22

    2019

  19. [26]

    Scott and P

    A. Scott and P. Seymour, A survey ofχ-boundedness,J. Graph Theory95(2020), 473–504

    2020

  20. [27]

    D. P. Sumner, Subtrees of a graph and the chromatic number, inThe Theory and Applications of Graphs, Wiley, New York, 1981, 557–576

    1981

  21. [28]

    D. B. West,Introduction to Graph Theory, Prentice Hall, Upper Saddle River, NJ, 1996

    1996

  22. [29]

    Wu and B

    D. Wu and B. Xu, Perfect divisibility and coloring of some fork-free graphs,Discrete Math.347 (2024), Article No. 114121

    2024

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.