Pith. sign in

REVIEW 3 major objections 5 minor 2 cited by

On minimal nonperfectly divisible fork-free graphs

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

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

Pith's one-line read Every minimal nonperfectly divisible fork-free graph is claw-free, reducing perfect divisibility of fork-free graphs to the claw-free case.

desk verdict A credible structural reduction for fork-free perfect divisibility, but the proof rests heavily on an unproved lemma from a submitted preprint. read the letter →

arxiv 2504.14863 v3 pith:FX4UBK2Y submitted 2025-04-21 math.CO

Baogang Xu , Miaoxia Zhuang This is my paper · ORCID
classification math.CO MSC 05C1505C75
keywords fork-freegraphsperfectdivisibilityclaw-freechromaticnumbercliqueoddholehomogeneoussetchi-boundedness
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

The paper works on perfect divisibility, a property that sits between ordinary coloring and perfect graphs: a graph is perfectly divisible if each induced subgraph can be split into a perfect part and a part whose clique number is strictly smaller. The open conjecture in this area is that every fork-free graph---a fork is a claw with one edge subdivided---is perfectly divisible. The paper's main theorem states that any minimal counterexample to that conjecture is claw-free. Since claw-free graphs are a subclass of fork-free graphs, that equivalence means the whole conjecture now stands or falls on claw-free graphs. The paper also settles two new cases, proving that every (fork, $P_7$)-free graph and every (fork, $P_6\cup K_1$)-free graph is perfectly divisible, and hence satisfies $\chi(G)\leq \binom{\omega(G)+1}{2}$.

What carries the argument

The load-bearing object is the decomposition of a minimal nonperfectly divisible fork-free graph around an odd hole $C$ inside $M(v)$. The paper partitions the rest of the graph into $M(C)$ (vertices anticomplete to $V(C)$), balloon centers $U$, parachute centers $U'$, and residual sets $Z,Z'$; the central identities are that each $U_i$ is a clique, $U'$ is complete to $U\cup V(C)\cup Y'\cup Z$, $Z'$ is a clique anticomplete to $U$, $M(C)\setminus Y'$ is a stable set, and $\omega(N(U_i\cup M(C)))\<\omega(G)$. These identities, together with the no-homogeneous-sets lemma, force a minimal counterexample to be odd-parachute-free and then claw-free. In Theorems 1.2 and 1.3, the same identities turn the forbidden induced path $P_7$ or $P_6\cup K_1$ into a contradiction, so the candidate sets form a perfect division.

What would settle it

The central claim is false exactly if some fork-free graph contains an induced claw and is itself not perfectly divisible while every proper induced subgraph is perfectly divisible; a search over small fork-free graphs with a claw, checking perfect divisibility of all proper induced subgraphs, would find such a counterexample if one exists.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 1.1: every minimal nonperfectly divisible fork-free graph is claw-free. The argument starts from a minimal counterexample $G$ and a vertex $v$ for which $G[M(v)]$ is not perfect, as guaranteed by Lemma 2.2; then $M(v)$ contains an odd hole $C$. Around $C$ the graph splits into balloon centers $U$ (vertices with exactly two consecutive neighbors on $C$ and at least one neighbor in $M(C)$), parachute centers $U'$ (complete to $C$), and the set $M(C)$ of vertices anticomplete to $V(C)$. The structural lemmas show that $M(C)\setminus Y'$ is a stable set, that $U'$ is complete to $U\cup V(C)\cup Y'\cup Z$, and that $N(U_i\cup M(C))$ has clique number strictly smaller than $\omega(G)$. These facts force every minimal nonperfectly divisible fork-free graph to contain no odd parachute, and then a claw centered at $v$ would imply $G[M(v)]$ is perfect, a contradiction. Thus no minimal fork-free counterexample has a claw, which makes perfect divisibility for fork-free graphs equivalent to perfect divisibility for claw-free graphs; Theorems 1.2 and 1.3 then prove the property for the $(P_7)$- and $(P_6\cup K_1)$-restricted classes.

Load-bearing premise

The argument rests on a lemma from the authors' preprint [10] saying that in a smallest graph that fails perfect divisibility, no nontrivial set of vertices can be one that every outside vertex either is connected to entirely or not at all; if that lemma fails, the later structural steps collapse.

Editorial extensions

If this is right

  • If the open conjecture fails for fork-free graphs, it fails for claw-free graphs; establishing perfect divisibility for claw-free graphs would settle the fork-free case.
  • Every (fork, $P_7$)-free graph is perfectly divisible, so $\chi(G)\leq \binom{\omega(G)+1}{2}$.
  • Every (fork, $P_6\cup K_1$)-free graph is perfectly divisible, so the same quadratic bound holds.
  • Minimal nonperfectly divisible fork-free graphs are odd-parachute-free, so any possible counterexample to the conjecture must avoid all odd parachutes as induced subgraphs.

Reading between the lines

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

  • Extension: the same odd-hole decomposition may serve as a template for other forbidden induced subgraphs $F$: one can test whether excluding $F$ from the fork-free class forces the mixed-on-$M(C)$ configurations to disappear, exactly as $P_7$ and $P_6\cup K_1$ do here.
  • Extension: Theorem 1.1 refocuses the unresolved conjecture on claw-free graphs; if the known structure theory for claw-free graphs can classify minimal nonperfectly divisible members, the full fork-free conjecture would follow without new fork-specific arguments.
  • Extension: a computational search over minimal nonperfectly divisible fork-free graphs on small vertex counts could independently test the no-homogeneous-sets lemma and the no-claw conclusion, giving a concrete check of the keystone assumption.
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 / 5 minor

Summary. The paper studies perfect divisibility, a relaxation of perfection in which every induced subgraph H admits a partition V(H)=A∪B with H[A] perfect and ω(H[B])<ω(H). The main result, Theorem 1.1, asserts that every minimal nonperfectly divisible fork-free graph is claw-free, which would reduce Sivaraman's conjecture that all fork-free graphs are perfectly divisible to the claw-free case. Theorems 1.2 and 1.3 prove that (fork,P7)-free and (fork,P6∪K1)-free graphs are perfectly divisible, giving the explicit bound χ(G)≤binom(ω(G)+1,2). The proofs use the structure of minimal counterexamples through odd holes, balloon centers, parachute centers, and homogeneous-set arguments.

Significance. If correct, the paper makes substantial progress on a known conjecture: Theorem 1.1 identifies the minimal obstruction to perfect divisibility in fork-free graphs as claw-free, and Theorems 1.2–1.3 extend the list of (fork,F)-free classes that are perfectly divisible. The χ-bound in Corollary 1.1 is explicit and quadratic. The paper is clearly organized, and the structural lemmas are stated with helpful figures. However, the central argument depends on an unproved external lemma from a submitted preprint and on several compressed case checks, so the manuscript in its current form does not yet provide a fully verifiable proof of the advertised results.

major comments (3)
  1. [Section 2, Lemma 2.1] The proof of the central theorems is not self-contained: Lemma 2.1 is quoted from the submitted preprint [10] and is used in the proofs of Lemma 2.8, Lemma 3.1, and Lemma 2.17, and therefore in Theorems 1.1–1.3. Since [10] is not yet refereed, the authors should include a proof of Lemma 2.1 in the present paper, or at minimum verify that the lemma has been accepted for publication and give the final citation. As it stands, the main results are contingent on an unproved external statement.
  2. [Section 2, Lemma 2.10] In the proof of the first assertion (Z' is a clique), the text states that {y_j,u_j,v_j,z'_1,z'_2} induces a fork, but at that point Z' is not known to be anticomplete to U. If z'_1 or z'_2 is adjacent to u_j, the set need not induce a fork. The second part of the lemma (Z' is anticomplete to U) is proved independently and should be proved first; after that, the clique proof becomes valid with v_j as the fork center. As written, the first step is unjustified.
  3. [Section 2, Lemma 2.17] The proof assumes failure of the conclusion for a fixed odd hole C, then derives the existence of a mixed u' for a new odd hole C'. The step 'By (2), there must exist a v′∈M(C′), ...' is not immediate, because (2) states that M(C) is a stable set, not that M(C′) is stable. The argument can be repaired by assuming the lemma false universally, or by explicitly applying the same derivation that led to (2) to the hole C′; as written, the contradiction does not follow from the stated supposition.
minor comments (5)
  1. [Section 1 and Section 2] The symbol M(v), and more generally M(X) for a set X, is used throughout but never defined in the paper. The intended meaning (the set of non-neighbors of v, respectively the set of vertices anticomplete to X) should be stated explicitly, since every subsequent lemma relies on it.
  2. [Section 2, Lemma 2.10] The cross-reference 'by Lemma ??' should be 'by Lemma 2.5', which is the lemma that guarantees U(C) is nonempty.
  3. [Section 3, Lemma 3.2, Claim 3.1] There is a duplicated word in the sentence 'Since U′ is complete to V (C)∪U∪Z∪Y′ by by Lemma 2.9'; 'by by' should be 'by'.
  4. [Section 2, Lemma 2.17 and Lemma 2.16] The reuse of the letter W for different sets is confusing: in Lemma 2.16, W is the set with smaller clique number, while in Lemma 2.17, W denotes the perfect side of the partition. Please use different letters or clarify the notation.
  5. [Section 3, Lemma 3.3] The proofs of Claims 3.2 and 3.3 are very terse; expanding the case analysis or adding a diagram of the induced forks would make the arguments substantially easier to verify.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the target theorems are derived from definitions and independent structural lemmas, not from the conclusions they purport to prove.

full rationale

The derivation chain in this paper is not circular. Theorems 1.1, 1.2, and 1.3 are proved by taking a minimal nonperfectly divisible fork-free graph, extracting an odd hole via Lemmas 2.2 and 2.3, and then using structural lemmas about the sets U, U', Y, Y', Z, Z' to force either a contradiction or a perfect division. The main imported results are Lemma 2.1 from the authors' submitted preprint [10] and Lemmas 2.3, 2.4, 2.5, and 2.12 from the overlapping-author paper [16]. These are parameter-free statements whose hypotheses (minimal nonperfectly divisible graphs, fork-free graphs, odd holes) do not include the target conclusions (minimal nonperfectly divisible fork-free graphs are claw-free; (fork,P7)-free and (fork,P6∪K1)-free graphs are perfectly divisible). They are used as building blocks rather than as renamed versions of the claims being established. No fitted parameter is later called a prediction, no quantity is defined in terms of the quantity it is used to derive, no uniqueness theorem is imported to forbid alternatives, and no known empirical pattern is merely renamed. The closest concern is that Lemma 2.1 is load-bearing and is not proved in this manuscript; it is used to show that certain sets are homogeneous sets and hence impossible in a minimal counterexample. However, reliance on an external cited lemma is a verification and correctness issue, not circularity, because the lemma does not reduce to the paper's own target statement. Under the hard rules, a cited result with stated assumptions that do not include the target result is independent support and does not raise the circularity score. Therefore the appropriate finding is no significant circularity.

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

No free parameters or invented entities. The paper is a pure proof; its load-bearing inputs are standard graph theory and four prior lemmas, two from overlapping-author papers.

assumptions (4)
  • domain assumption A minimal nonperfectly divisible graph has no homogeneous set (Lemma 2.1 of [10]).
    Imported from a submitted arXiv preprint by the same group; used to prove M(C)\Y' is a stable set (Lemma 2.8) and |Y|=1 (Lemma 3.1).
  • domain assumption If every graph in a hereditary class has a vertex whose anti-neighborhood is perfect, then every graph in the class is perfectly divisible (Lemma 2.2 of [11]).
    Used to force G[M(v)] to be non-perfect in a minimal counterexample; also used in the proof of Theorem 1.1.
  • domain assumption Structural lemmas for fork-free minimal nonperfectly divisible graphs from Wu-Xu [16] (Lemmas 2.3, 2.4, 2.5).
    Provide odd-hole restrictions, the two-consecutive-or-complete partition of N(M(C)), and U not empty; [16] has an overlapping author with this paper.
  • standard math Strong Perfect Graph Theorem: a graph is perfect iff it has no odd hole and no odd antihole.
    Used implicitly through Lemma 2.3 when concluding that a non-perfect G[M(v)] contains an odd hole.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On minimal nonperfectly divisible fork-free graphs." pith.science (2026). https://pith.science/paper/FX4UBK2Y

@misc{pith2026250414863,
  author       = {Pith},
  title        = {Pith review of: On minimal nonperfectly divisible fork-free graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FX4UBK2Y}},
  note         = {Machine review of arXiv:2504.14863}
}
abstract

A fork is a graph obtained from $K_{1,3}$ (usually called claw) by subdividing an edge once. 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)$. In this paper, we prove that the perfect divisibility of fork-free graphs is equivalent to that of claw-free graphs. We also prove that, for $F\in \{P_7, P_6\cup K_1\}$, each (fork, $F$)-free graph $G$ is perfectly divisible and hence $\chi(G)\leq \binom{\omega(G)+1}{2}$.

Figures

Figures reproduced from arXiv: 2504.14863 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 ↗
Figure 2
Figure 2. A simple illustration of the sets V (C), U, U′ , Z, Z′ and M(C) etc. the rest of the discussion, when referring to the odd hole C and in the absence of ambiguity, we simply write U(C), U′ (C), Y (C), Y ′ (C), Z(C), Z′ (C), Ui(C) as U, U′ , Y, Y ′ , Z, Z′ , Ui respectively, where i ∈ {1, 2, ..., n}. See [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Every fork-free graph is perfectly weight divisible

    math.CO 2026-08 conditional novelty 8.0 of 10

    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.

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

    math.CO 2025-05 reject novelty 5.0 of 10

    The authors prove, with a proof gap, that every (fork, antifork∪K1)-free graph is perfectly divisible, implying χ(G) ≤ binom(ω(G)+1, 2).

Reference graph

Works this paper leans on

16 extracted references · 5 canonical work pages · cited by 2 Pith papers

  1. [10]

    Q. Hu, B. Xu and M. Zhuang, Perfect weighted divisibility is equivalent to perfect divisibility, submitted. (Available at http://arxiv.org/abs/2504.13695)

    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

    2024

  3. [2]

    Brause, B

    C. Brause, B. Randerath, I. Schiermeyer and E. Vumar, 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. 12

    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 IV - Decomposition theorem, Journal of Com- binatorial Theory, Series B 98 (2008) 839-938

    work page 2008

  7. [6]

    Chudnovsky and P

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

    2010

  8. [7]

    Chudnovsky and V

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

    work page 2019

Show all 16 references
  1. [8]

    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

    1973

  2. [9]

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

    2018

  3. [11]

    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

  4. [12]

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

    1995

  5. [13]

    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

  6. [14]

    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

  7. [15]

    Scott and P

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

    2020

  8. [16]

    Wu and B

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

    2024

Pith tools

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