REVIEW 6 minor 1 cited by
On the structure of perfectly divisible graphs
T0 review · 0 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read The paper proves that P5-free minimally non-perfectly-divisible graphs cannot contain a clique cutset, a structural restriction that re-establishes perfect divisibility for (P5, C5, K2,3)-free graphs, and that recognizing perfectly…
desk verdict Hoàng's clique-cutset theorem for P5-free MNPD graphs is correct, novel, and worth a serious referee; two terse steps in the proof need minor patching. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central mechanism is the fusing of good partitions across a clique cutset, powered by two standard facts: Lemma 1.1 (no minimal imperfect graph contains a clique cutset, cited from [9]) and the Strong Perfect Graph Theorem that an imperfect graph contains an odd hole or odd antihole. The $P_5$-free hypothesis is what makes the fusion work: any obstruction that reaches across the cut must, together with a neighbor of the cut, induce a $P_5$, which is forbidden. This turns the question of perfect divisibility of a $P_5$-free class into a purely structural statement about cutset-free MNPD graphs.
What would settle it
Find a $P_5$-free graph $G$ that is minimally non-perfectly-divisible and has a clique cutset; since being MNPD is a property checkable on a single finite graph, an exhaustive search over small $P_5$-free graphs with clique cutsets would produce one if it exists, refuting Theorem 1.4.
Extended reading notes
Core claim
On the paper's own terms, Theorem 1.4 states that a $P_5$-free MNPD graph cannot contain a clique cutset. The proof takes a minimal clique cutset $C$ separating the rest of the graph into $V_1$ and $V_2$, obtains good partitions $(A_i, B_i)$ on each side $G_i = G[C \cup V_i]$, and fuses them into $(A, B)$. If $G[A]$ were imperfect, it would contain an odd hole or odd antihole $H$; since the fused cut $C_A = (A_1 \cap C) \cup (A_2 \cap C)$ is a clique cutset of $G[A]$ and minimal imperfect graphs have no clique cutsets (Lemma 1.1), $H$ must lie entirely on one side. $P_5$-freeness then forces a vertex of $A_1 \cap C$ to have a neighbor in $V_1$, and the obstruction $H$ together with that neighbor produces an induced $P_5$, a contradiction. An analogous argument (Theorem 1.5) shows that a $4K_1$-free MNPD graph cannot contain a clique cutset. The same framework yields Theorem 3.2: a triangle-free graph is perfectly divisible if and only if it is 3-colorable, so recognizing perfectly divisible graphs is NP-hard.
Load-bearing premise
The proof depends on the cited folklore lemma that no minimally imperfect graph has a clique cutset, which the paper does not prove; if an odd antihole could have a clique cutset, the contradiction construction in Theorem 1.4 would not close.
Editorial extensions
If this is right
- The theorem re-establishes the result of Dong, Xu and Yu that $(P_5, C_5, K_{2,3})$-free graphs are perfectly divisible, without relying on their flawed proof of the clique-cutset conjecture.
- Any $P_5$-free minimal counterexample to perfect divisibility is a graph with no clique cutset, so proofs for $P_5$-free classes can assume the graph is not separable by a clique.
- For triangle-free graphs, perfectly divisible is exactly the same as 3-colorable; hence deciding perfect divisibility is NP-hard even in this restricted class.
- The $4K_1$-free version gives a cutset-free structure for minimal counterexamples with stability number at most three, supporting the conjecture that graphs with $\alpha(G) \le 3$ are perfectly divisible.
Reading between the lines
- The proof template suggests a general strategy: for any hereditary class, showing that MNPD graphs have no clique cutsets reduces perfect divisibility to analyzing the non-separable members of the class; the same partition-fusion argument might work for other forbidden induced subgraphs besides $P_5$.
- The equivalence between perfect divisibility and 3-colorability on triangle-free graphs means the class of perfectly divisible graphs contains a computationally hard core, so any polynomial recognition algorithm would imply P = NP (under the usual assumption).
- If Conjecture 1.2 (no MNPD graph has a clique cutset) fails, the failure must occur outside $P_5$-free and $4K_1$-free graphs; the counterexample would have both an odd hole/antihole interaction and a clique cutset that does not create a $P_5$.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies perfectly divisible graphs, a relaxation of perfect graphs introduced by Hoàng. Its main theorem states that a P5-free minimally non-perfectly divisible (MNPD) graph cannot contain a clique cutset (Theorem 1.4), and a second theorem gives the same conclusion for 4K1-free MNPD graphs (Theorem 1.5). The paper also proves that recognizing perfectly divisible graphs is NP-hard by a reduction from 3-coloring triangle-free graphs (Theorem 3.2), and it points out an error in a proof by Dong, Xu and Yu of a related result. Several conjectures on perfect divisibility and 2-divisibility are proposed.
Significance. Theorem 1.4 is a structural restriction on MNPD graphs that confirms Conjecture 1.2 in the P5-free case, and it can be used to re-establish the previously claimed theorem that (P5, C5, K2,3)-free graphs are perfectly divisible. The proof is direct and transparent: it uses only the Strong Perfect Graph Theorem, the folklore lemma that minimal imperfect graphs have no clique cutset, and explicit P5-avoidance arguments. There are no free parameters, no circular steps, and no fitted assumptions. The NP-hardness result is clean, as it is an equivalence between perfect divisibility and 3-colorability on triangle-free graphs. If the few terse points in the main proof are clarified, the paper will be a solid contribution.
minor comments (6)
- [Section 2, proof of Theorem 1.4] The assertion that C_A = (A1∩C) ∪ (A2∩C) is a clique cutset of G[A] is not true when one of A1\C or A2\C is empty. In that case the desired conclusion that an odd hole or antihole H cannot contain vertices from both V1 and V2 is automatic, but the proof should state this explicitly.
- [Section 2, odd antihole case in Theorem 1.4] The existence of vertices h1, h2, h3 outside C with edges h1h2, h2c, ch3 in the complement H̄ is stated without proof. It follows because C∩V(H) is a stable set of an odd cycle with no two consecutive vertices, so deleting C leaves a path of length at least two adjacent to some c∈C; a one-line justification should be added.
- [Section 2, proof of Lemma 2.3] The argument that every induced subgraph G' of G[A] is perfect is compressed. In particular, when G' contains vertices from both V1 and V2, the separating clique cutset is A2∩C∩V(G'), and if this set is empty then G' is disconnected; these cases should be spelled out.
- [Section 2, Lemmas 2.1 and 2.2] The phrase 'Since G-x is perfectly divisible, its vertex set admits a good partition' implicitly assumes G-x has at least one edge. When G-x is edgeless, a trivial separate argument yields the desired partition; this should be noted for completeness, even though these lemmas are not used in the main theorems.
- [Section 3, proof of Theorem 3.2] The proof is sound, but it should state explicitly that the WLOG assumption that G has at least one edge is used to guarantee ω(G)=2 in the reverse implication; this is currently implicit.
- [References and Figure 1] Reference [14] is dated 2002, but volume 29 of the Electronic Journal of Combinatorics corresponds to 2022; please correct the year. Also, the in-text citation 'Dong, Xu and Yu' for [7] does not match the reference list entry 'Dong, W., Xu, B. and Xu, Y.'; the names should be made consistent. Finally, Figure 1 is referenced but does not appear in the text provided; please ensure the figure is present in the published version.
Circularity Check
No significant circularity: the proof of Theorem 1.4 derives the clique-cutset obstruction directly from the MNPD definition and standard external theorems, with no fitted inputs or load-bearing self-citations.
full rationale
The central derivation is self-contained. In Theorem 1.4, the author starts from a P5-free MNPD graph G with a clique cutset C, takes the two sides V1 and V2, and uses the minimality of G to obtain good partitions of G[C∪V1] and G[C∪V2]. The proof that the assembled partition (A,B) is good is a direct combinatorial argument: largest cliques lie wholly in one side and are met by the appropriate A_i, so G[B] has no clique of size ω(G). If G[A] were imperfect, the Strong Perfect Graph Theorem supplies an induced odd hole or odd antihole H. The claim that H cannot meet both V1 and V2 uses the external folklore Lemma 1.1 (cited to Golumbic) that minimal imperfect graphs have no clique cutset; odd holes and odd antiholes are minimal imperfect, so this is valid external support rather than circular reasoning. The subsequent contradictions in the odd-hole and odd-antihole cases are explicit P5 constructions that do not rely on the conclusion being proved. Lemma 2.3 similarly applies Lemma 1.1 to rule out a minimal imperfect induced subgraph with a clique cutset, and Theorem 3.2 reduces recognition to 3-coloring triangle-free graphs via a direct equivalence, using the external NP-hardness result of Maffray and Preissmann. The author's own prior work is cited only for definitions, conjectures, and context, not as a load-bearing resource. No fitted parameter is renamed as a prediction, and no equation is equivalent to its input by construction.
Assumptions & free parameters
assumptions (5)
- standard math Strong Perfect Graph Theorem: a graph is perfect iff it contains no odd hole and no odd antihole.
- standard math Folklore Lemma 1.1: no minimal imperfect graph contains a clique cutset.
- standard math Odd holes and odd antiholes are minimal imperfect graphs.
- standard math The complement of a bipartite graph is perfect.
- standard math NP-hardness of 3-colorability of triangle-free graphs.
Cite this review
Pith. "Pith review of On the structure of perfectly divisible graphs." pith.science (2026). https://pith.science/paper/EJVPXTDG
@misc{pith2026250612660,
author = {Pith},
title = {Pith review of: On the structure of perfectly divisible graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/EJVPXTDG}},
note = {Machine review of arXiv:2506.12660}
}
abstract
A graph $G$ is perfectly divisible if every induced subgraph $H$ of $G$ contains a set $X$ of vertices such that $X$ meets all largest cliques of $H$, and $X$ induces a perfect graph. The chromatic number of a perfectly divisible graph $G$ is bounded by $\omega^2$ where $\omega$ denotes the number of vertices in a largest clique of $G$. A graph $G$ is minimally non-perfectly divisible if $G$ is not perfectly divisible but each of its proper induced subgraph is. A set $C$ of vertices of $G$ is a clique cutset if $C$ induces a clique in $G$, and $G-C$ is disconnected. We prove that a $P_5$-free minimally non-perfectly divisible graph cannot contain a clique cutset. This result allows us to re-establish several theorems on the perfect divisibility of some classes of $P_5$-free graphs. We will show that recognizing perfectly divisible graphs is NP-hard.
Figures
Forward citations
Cited by 1 Pith paper
-
Perfect divisions in ($P_2 \cup P_4$, bull)-free graphs
Every (P2∪P4, bull)-free graph with clique number at least 3 and no homogeneous set admits a perfect division.
Reference graph
Works this paper leans on
-
[1]
Berge, F¨ arbung von Graphen, deren s¨ amtliche bzw
C. Berge, F¨ arbung von Graphen, deren s¨ amtliche bzw. deren ungerade Kreise starr sind,Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.- Natur. Reihe10:114 (1961) 88
work page 1961
-
[2]
C. Berge and V. Chv´ atal (eds.), Topics on perfect graphs. North-Holland, Amsterdam, 1984
work page 1984
-
[3]
M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, The strong perfect graph theorem,Annals of Mathematics164 (2006), pp. 51–229
work page 2006
-
[4]
M. Chudnovsky, and P. Seymour. Even-hole-free graphs still have bisim- plicial vertices.Journal of Combinatorial Theory, Series B, 161 (2023): 331-381
work page 2023
-
[5]
M. Chudnovsky, and V. Sivaraman. Perfect divisibility and 2-divisibility. Journal of Graph Theory, 90.1 (2019): 54-60
work page 2019
-
[6]
W. Dong, J.-L. Song, and B. Xu. 2-divisibility of Some Odd Hole Free Graphs.Acta Mathematicae Applicatae Sinica, English Series38.3 (2022): 710-718
work page 2022
-
[7]
W. Dong, B. Xu and Y. Xu. On the chromatic number of someP 5-free graphsDiscrete Mathematics345.10 (2022). https://doi.org/10.1016/j.disc.2022.113004
arXiv 2022
-
[8]
M. R. Garey, and D. S. Johnson. Computers and intractability. Vol. 29. New York: Freeman, 2002
work page 2002
Show all 17 references
-
[9]
M. C. Golumbic, Algorithmic graph theory and perfect graphs, Academic Press, New York, 1980
1980
-
[10]
C. T. Ho` ang. On the structure of (banner, odd hole)-free graphs.Journal of Graph Theory89.4 (2018): 395-412
2018
-
[11]
C. T. Ho` ang and C. McDiarmid, A note on the divisibility of graphs, in: Congressus Numerantium 136, Proceedings of the Thirtieth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (1999), 215-219
1999
-
[12]
C. T. Ho` ang and C. McDiarmid, On the divisibility of graphs,Discrete Mathematics242 (2002), 145–156
2002
-
[13]
C. T. Ho` ang, R. Srithara. Perfect graphs, in: Handbook of Graph Theory, Combinatorial Optimization, and Algorithms, K. Thulasiraman, S. Aru- mugam, A. Brandst¨ adt, T. Nishizeki (eds), CRC Press, 2015
2015
-
[14]
Karthick, J
T. Karthick, J. Kaufmann, and V. Sivaraman. Coloring Graph Classes with no Induced Fork via Perfect Divisibility.Electronic Journal of Com- binatorics29:2 (2002). 7
2002
-
[15]
Maffray, M
F. Maffray, M. Preissmann, On the NP-completeness of the k-colorability problem for triangle-free graphs,Discrete Mathematics162 (1996), 313– 317
1996
-
[16]
J. L. Ramirez Alfonsin and B. Reed (Eds.), Perfect graphs, Wiley (2001)
2001
-
[17]
Vuˇ skovi´ c, Even-hole-free graphs: A survey, Appl
K. Vuˇ skovi´ c, Even-hole-free graphs: A survey, Appl. Anal. Discrete Math. 4 (2010), 219–240. Statements and Declarations The author acknowledges the support of the Natural Sciences and Engineer- ing Research Council of Canada (NSERC), [funding reference number DDG- 2024-000...
2010
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.