Pith. sign in

REVIEW 3 major objections 4 minor 15 references

Perfect divisibility of (fork, antifork$\cup K_1$)-free graphs

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

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

Pith's one-line read The paper proves that every (fork, antifork∪K1)-free graph is perfectly divisible, and consequently that every such graph has chromatic number at most binomial(ω(G)+1, 2).

desk verdict New result on perfect divisibility for a subclass of fork-free graphs, but the proof as written has a real gap in statement (M1); likely repairable, but it needs a serious rewrite before publication. read the letter →

arxiv 2505.04429 v1 pith:DUKIBQBB submitted 2025-05-07 math.CO

Ran Chen , Baogang Xu , Miaoxia Zhuang This is my paper · ORCID
classification math.CO MSC 05C1505C75
keywords fork-freegraphsperfectdivisibilitychromaticnumbercliqueantiforkχ-boundednessoddholeclaw-free
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

A fork is a claw with one edge subdivided, and an antifork is the complement of a fork; the class studied forbids both induced forks and induced antifork-plus-isolated-vertex graphs. The paper proves that every graph in this class is perfectly divisible: each induced subgraph $H$ can be split into a perfect part and a part whose clique number is strictly smaller than $\omega(H)$. The theorem improves known results on (fork, co-cricket)-free graphs, because a co-cricket is an induced subgraph of an antifork plus an isolated vertex, and the earlier work only showed those graphs are either claw-free or perfectly divisible. The immediate corollary is a quadratic $\chi$-binding function: $\chi(G) \le \binom{\omega(G)+1}{2}$ for every such graph.

What carries the argument

The engine of the proof is a minimal non-perfectly-divisible counterexample, and inside it a shortest odd hole $C_0$ lying in the non-neighborhood $M(v_0)$ of some vertex $v_0$. Around $C_0$ the vertices are partitioned into $U$ (vertices with exactly two consecutive neighbors on $C_0$ and at least one neighbor outside), $Z$ (outside $U$, with some but not all neighbors on $C_0$), $Z'$ (complete to $C_0$), and $M(C_0)$. The structural lemmas (M1)--(M9) control this partition: they make $Z'$ a clique anticomplete to $U\cup Z$, make each $U_i\cup Z_i$ a clique, forbid most edges between classes, and force clique-number drops. These constraints yield the explicit perfect division $A = A_0 \cup V_{\mathrm{odd}} \cup S$, $B = B_0 \cup (U\setminus S)\cup Z\cup V_{\mathrm{even}}\cup Z'$, where $(A_0,B_0)$ is a perfect division of $G[M(C_0)]$.

What would settle it

Enumerate the local configuration used in (M1): if a vertex $z$ has exactly three consecutive neighbors $v_i,v_{i+1},v_{i+2}$ on the odd hole and no other neighbors, then $G[N(z)\cup\{v,z\}]$ has only five vertices for $v\in M(C_0)$, so it cannot contain the six-vertex graph $\mathrm{antifork}\cup K_1$; if $z$ has four consecutive neighbors, the degree sequence of the claimed induced subgraph is $(4,3,3,2,2,0)$, not the $(3,3,3,2,1,0)$ of $\mathrm{antifork}\cup K_1$. These two direct checks settle whether the key conclusion $Z=\bigcup_i Z_i$ follows from the stated argument.

Watch

Extended reading notes

Core claim

The central claim, Theorem 1.2, is that every (fork, antifork∪K1)-free graph is perfectly divisible; the proof obtains the corollary $\chi(G) \le \binom{\omega(G)+1}{2}$. A fork is a claw with one edge subdivided, and an antifork is the complement of a fork, so antifork∪K1 is an antifork together with an isolated vertex. The argument starts from a minimal non-perfectly-divisible counterexample, which is known to be claw-free. Fixing a shortest odd hole $C_0$ in the graph induced by vertices that are neither $v_0$ nor adjacent to $v_0$, the authors separate the remaining vertices into the classes $U$ (vertices with exactly two consecutive neighbors on $C_0$ but with neighbors outside), $Z$ (vertices outside $U$ with at least one but not all neighbors on $C_0$), $Z'$ (vertices complete to $C_0$), and $M(C_0)$. Nine structural claims (M1)--(M9) constrain how these classes can attach to $C_0$, and from those constraints a perfect division is built explicitly as $A = A_0 \cup V_{\mathrm{odd}} \cup S$ and $B = B_0 \cup (U\setminus S) \cup Z \cup V_{\mathrm{even}} \cup Z'$.

Load-bearing premise

The proof's load-bearing step is the claim that a vertex with three or four consecutive neighbors on the chosen shortest odd hole necessarily creates an induced antifork∪K1, and this claim is not supported by a vertex count in the three-neighbor case or by a degree-sequence match in the four-neighbor case.

Editorial extensions

If this is right

  • Every (fork, antifork∪K1)-free graph $G$ satisfies $\chi(G) \le \binom{\omega(G)+1}{2}$, making the class polynomially $\chi$-bounded with a quadratic binding function.
  • Every (fork, co-cricket)-free graph is perfectly divisible, since a co-cricket is an induced subgraph of an antifork∪K1; previously these graphs were known only to be either claw-free or perfectly divisible.
  • The theorem verifies the perfect-divisibility conjecture for fork-free graphs on the subfamily obtained by additionally forbidding antifork∪K1, adding to the known forbidden subgraphs for which the conjecture holds.
  • Because perfect divisibility is a hereditary property, every induced subgraph of a graph in this class inherits the same quadratic chromatic bound.

Reading between the lines

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

  • If the theorem is correct, the same partition strategy may extend to all fork-free graphs: the proof's work happens entirely around a shortest odd hole, so the antifork∪K1 condition may be replaceable by a milder constraint on how vertices attach to that hole.
  • The bound $\binom{\omega(G)+1}{2}$ is probably not sharp; searching for (fork, antifork∪K1)-free graphs whose chromatic number approaches it would test whether a smaller quadratic or even linear binding function exists.
  • The structural claims (M1)--(M9) are local and checkable, so a computational search over small graphs could verify the classification of attachment classes and refine the proof before attempting the full fork-free conjecture.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

Summary. The paper claims to prove that every (fork, antifork∪K1)-free graph is perfectly divisible, yielding the corollary χ(G) ≤ binom(ω(G)+1,2). The proof proceeds by assuming a minimal nonperfectly divisible counterexample, selecting a shortest odd hole C0 in G[M(v0)], and partitioning the remaining vertices into classes U, Z, Z′. The crucial step (M1) asserts that the set Z is exactly the union of the Z_i, where each Z_i consists of vertices with exactly two consecutive neighbors on C0. Subsequent claims (M4), (M8), (M9), and Claim 2.1 rely on this partition. The paper also depends on Lemmas 2.3–2.5 from a submitted preprint by two of the authors.

Significance. If correct, the result would constitute a significant step toward Karthick et al.'s conjecture that fork-free graphs are perfectly divisible, and it would improve known bounds for (fork, co-cricket)-free graphs. However, the proof contains a load-bearing gap in (M1): the asserted existence of an induced antifork∪K1 in G[N(z)∪{v,z}] for a vertex z with three consecutive neighbors on C0 is false as stated. Because this gap invalidates the partition Z = ∪ Zi, the correctness of the main theorem is not established in this manuscript. Additionally, the heavy reliance on unpublished lemmas from [15] makes the proof not self-contained. The claimed result may be true, but the present proof does not support it.

major comments (3)
  1. [§2, (M1)] The statement 'as otherwise G[N(z)∪{v,z}] contains an antifork∪K1' is false for the three-consecutive-neighbor case. If N_{C0}(z) = {v_i, v_{i+1}, v_{i+2}}, then since z∈Z is anticomplete to M(C0) and v∈M(C0), the vertex set of G[N(z)∪{v,z}] consists of z, v, and the three neighbors. This gives only five vertices, while antifork∪K1 has six vertices. Even if N(z) contains additional vertices outside C0, the proof provides no argument that such vertices exist or that they yield the forbidden induced subgraph. A concrete witness (C5 with z adjacent to three consecutive vertices and v isolated) satisfies the local assumptions but contains no antifork∪K1. Since (M1) establishes the partition Z=∪Z_i used in (M4), (M8), (M9), and Claim 2.1, this gap invalidates the proof of Theorem 1.2.
  2. [§2, (M1)] The two-pair case in (M1) is not rigorously justified. The text claims that if N(z)∩V(C0) = {v_i, v_{i+1}, v_j, v_{j+1}} with j∈{i+3,...,i−3}, then either v_{i+1}v_{i+2}···v_j z or v_i v_{i−1}···v_{j+1} z is an odd hole in M(v0) of length less than |V(C0)|. This requires verifying that the chosen cycle is induced, that it indeed lies in M(v0), and that its length is odd and strictly smaller than n. None of these steps is shown. Even if this case could be repaired, the three-consecutive-neighbor case already breaks the proof of (M1).
  3. [§2, Lemmas 2.3–2.5] The proof depends essentially on Lemmas 2.3, 2.4, and 2.5 from [15], a submitted preprint by two of the present authors. These lemmas are not proved in this manuscript, so the paper is not self-contained. The referees cannot verify the correctness of the central argument without access to a published or otherwise available version of [15]. The authors should either include proofs of these lemmas or cite a published version before the paper can be considered.
minor comments (4)
  1. [Abstract and Introduction] There are several typos: 'satisfies that satisfies that' in the introduction, and 'confirmed a conjecture a conjecture' in the introduction.
  2. [§2, (M1)] The formula 'Z = S^2_{i=1} Z_i' appears to be a typo; it should presumably be 'Z = ⋃_{i=1}^n Z_i'.
  3. [§2, (M6)] In the sentence beginning 'If N_{M(C0)}(u_i) ≠ N_{M(C0)}(u_j)', the expression 'G[{y,u_i,u_j,t_1} is a claw' is missing a closing bracket; it should be 'G[{y,u_i,u_j,t_1}]'.
  4. [References] The introduction cites Karthick et al. as 'Electron. J. Comb. 28 (2021), P2.20', while the reference list gives '29 (2022), P3.19'. These should be reconciled.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: Theorem 1.2 is derived from independent structural lemmas; the same-author lemmas in [15] are not equivalent to the target result.

full rationale

The paper's derivation does not reduce to its inputs. Theorem 1.2 is proved by taking a minimal nonperfectly divisible (fork, antifork∪K1)-free graph, invoking standard Lemma 2.1, Lemma 2.2 from [14], and Lemmas 2.3–2.5 from [15] (Xu–Zhuang, submitted). Although [15] is by two of the present authors, those lemmas are independent structural statements about minimal nonperfectly divisible fork-free graphs (e.g., Lemma 2.4: such graphs are claw-free); they are parameter-free and do not assume the desired (fork, antifork∪K1)-free perfect divisibility, so they are independent evidence rather than a circular input. The remaining proof partitions V(G) using C0, U, Z, Z', constructs A and B from a perfect division (A0,B0) of M(C0), and verifies ω(G[B])<ω(G) and G[A] perfect through clique/anticomplete arguments (M1–M9, Claims 2.1–2.3) rather than by citing the theorem. No fitted parameter is renamed as a prediction and no uniqueness theorem is imported to force the conclusion. One scoring concern: the assertion in (M1) that, when z has three or four consecutive neighbors on C0, 'as otherwise G[N(z)∪{v,z}] contains an antifork∪K1' appears unsupported as stated — with three consecutive neighbors the induced subgraph on N(z)∪{v,z} has only five vertices while the forbidden graph has six, and with four consecutive neighbors the degree sequence is incompatible — but this is a local correctness gap, not a circularity, and does not change the circularity verdict.

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

The proof depends on six external lemmas, four of which are from a submitted preprint by the present authors (Xu and Zhuang [15]). No free parameters or invented entities are introduced. The reliance on [15] is a significant dependency because that preprint is not yet peer-reviewed.

assumptions (6)
  • standard math Strong Perfect Graph Theorem (Theorem 1.1): a graph is perfect iff it has no odd hole and no odd antihole.
    Used to assert that the non-perfect graph G[M(v0)] contains an odd hole or odd antihole.
  • domain assumption Lemma 2.1 from Karthick et al. [9]: if every graph in a hereditary class has a vertex v with H[M(v)] perfect, then every graph in the class is perfectly divisible.
    Used to reduce to a minimal counterexample where G[M(v0)] is not perfect.
  • domain assumption Lemma 2.2 from Wu and Xu [14]: in a minimal non-perfectly divisible fork-free graph, M(v) contains no odd antihole except C5.
    Used to conclude that G[M(v0)] contains an odd hole.
  • domain assumption Lemma 2.3 from Xu and Zhuang [15]: adjacency pattern on odd holes in minimal non-perfectly divisible fork-free graphs.
    Used to assert U = union of Ui, a key step in the decomposition.
  • domain assumption Lemma 2.4 from Xu and Zhuang [15]: every minimal non-perfectly divisible fork-free graph is claw-free.
    This is a load-bearing structural reduction; it comes from a submitted preprint by two of the present authors.
  • domain assumption Lemma 2.5 from Xu and Zhuang [15]: classification of the neighborhood of a vertex in Z on the shortest odd hole.
    Used in the proof of (M1) to enumerate possible neighborhoods of z in Z.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Perfect divisibility of (fork, antifork$\cup K_1$)-free graphs." pith.science (2026). https://pith.science/paper/DUKIBQBB

@misc{pith2026250504429,
  author       = {Pith},
  title        = {Pith review of: Perfect divisibility of (fork, antifork$\cup K_1$)-free graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DUKIBQBB}},
  note         = {Machine review of arXiv:2505.04429}
}
abstract

A {\em fork} is a graph obtained from $K_{1,3}$ (usually called {\em claw}) by subdividing an edge once, an {\em antifork} is the complement graph of a fork, and a {\em co-cricket} is a union of $K_1$ and $K_4-e$. A graph is perfectly divisible if for each of its induced subgraph $H$, $V (H)$ can be partitioned into $A$ and $B$ such that $H[A]$ is perfect and $\omega(H[B]) < \omega(H)$. Karthick {\em et al.} [Electron. J. Comb. 28 (2021), P2.20.] conjectured that fork-free graphs are perfectly divisible, and they proved that each (fork, co-cricket)-free graph is either claw-free or perfectly divisible. In this paper, we show that every (fork, {\em antifork}$\cup K_1$)-free graph is perfectly divisible. This improves some results of Karthick {\em et al.}.

Figures

Figures reproduced from arXiv: 2505.04429 by the authors.

Figure 1
Figure 1. Illustration of fork and some forbidden configurations. [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 13 canonical work pages

  1. [15]

    Xu and M

    B. Xu and M. Zhuang, On minimal nonperfectly divisible fork-free graphs, submitted. (Available at http://arxiv.org/abs/2504.14863) 9

    arXiv

  2. [1]

    Bria´ nski, J

    M. Bria´ nski, J. G. Davies and B. Walczak, Separating polynomial χ-boundedness from χ- boundedness, Combinatorica 44 (2024), no. 1, 1–8

    work page 2024

  3. [2]

    Brause, B

    C. Brause, B. Randerath, I. Schiermeyer and E. Vumar, On the chromatic number of 2 K2-free graphs, Discrete Applied Mathematics 253 (2019) 14–24

    work page 2019

  4. [3]

    Char and T

    A. Char and T. Karthick, χ-boundedness and related problems on graphs without long induced paths: A survey, Discrete Applied Mathematics 364 (2025) 99–119

    work page 2025

  5. [4]

    Chudnovsky, N

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

    2006

  6. [5]

    Chudnovsky and P

    M. Chudnovsky and P. Seymour, Claw-free graphs VI. Colouring, Journal of Combinatorial The- ory, Series B 100 (2010) 560-572

    work page 2010

  7. [6]

    Chudnovsky and V

    M. Chudnovsky and V. Sivaraman, Perfect divisibility and 2-divisibility, Journal of Graph Theory 90 (2019) 54-60. 8

    work page 2019

  8. [7]

    Gy´ ar´ as, On Ramsey Covering-Numbers, Colloquium, Keszthely, 1973; dedicated to P

    A. Gy´ ar´ as, On Ramsey Covering-Numbers, Colloquium, Keszthely, 1973; dedicated to P. Erd¨ os on his 60th birthday, vol. II, Colloquia Mathematica Societatis J´ anos Bolyai, vol. 10, North-Holland, Amsterdam, 1975, pp. 801-816

    work page 1973

Show all 15 references
  1. [8]

    C. T. Ho` ang, On the structure of (banner, odd hole)-free graphs, Journal of Graph Theory 89 (2018) 395-412

    2018

  2. [9]

    Karthick, J

    T. Karthick, J. Kaufmann and V. Sivaraman, Coloring graph classes with no induced fork via perfect divisibility, Electronic Journal of Combinatorics 29 (2022), P3.19

    2022

  3. [10]

    J. H. Kim, The Ramsey number R(3,t ) has order of magnitude O( t2 logt ), Random Structures Algorithms 7 (1995) 173-207

    1995

  4. [11]

    X. Liu, J. Schroeder, Z. Wang and X. Yu, Polynomial χ-binding functions fort-broom-free graphs, Journal of Combinatorial Theory, Series B 162 (2023) 118-133

    2023

  5. [12]

    Schiermeyer and B

    I. Schiermeyer and B. Randerath, Polynomial χ-binding functions and forbidden induced sub- graphs: A survey, Graphs and Combinatorics 35 (2019) 1-31

    2019

  6. [13]

    Scott and P

    A. Scott and P. Seymour, A survey of χ-boundedness, Journal of Graph Theory 95 (2020) 473-504

    2020

  7. [14]

    Wu and B

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

    2024

Pith tools

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