{"id":"7b2923e9-f483-4b39-973d-b9665a3bbd99","arxiv_id":"2506.12660","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A P5-free minimally non-perfectly divisible graph cannot contain a clique cutset, and recognizing perfectly divisible graphs is NP-hard.","lead":"This paper proves that P5-free minimal counterexamples to perfect divisibility cannot contain a clique cutset, and that recognizing perfectly divisible graphs is NP-hard. The result repairs a flawed earlier proof and provides a structural tool for open conjectures about perfect graphs.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the central proof is correct; the odd-antihole existence assertion and the empty-side clique-cutset edge case need explicit one-line justifications but do not threaten Theorem 1.4.","rationale":"The reader's weakest_assumption focuses on Lemma 1.1, but that lemma is standard, cited to a textbook, and directly applicable to the odd holes and odd antiholes used in the proof; it is not a genuine load-bearing weakness. The two genuinely compressed steps are the empty-side clique-cutset statement and the unproved existence of three non-C vertices in the complement cycle. Both are real presentation gaps, but each is true and admits a short repair. Because the central claim survives scrutiny and the identified issues are minor and local, the reader's CONDITIONAL verdict should stand. I agree with the reader that the paper is essentially correct, and I partially agree with the reader's diagnosis: the flagged empty-side issue is present, but the alleged reliance on Lemma 1.1 is not a soft spot. The cleanest check is to verify the missing combinatorial lemma explicitly, which then closes the only step whose validity is not immediately transparent from the written proof.","tokens_in":5674,"tokens_out":28971,"duration_ms":349402,"concrete_test":"Formalize the missing combinatorial lemma: for every odd n ≥ 7 and every nonempty stable set C in the cycle C_n, prove there exist c ∈ C and h1,h2,h3 ∉ C with h1h2, h2c, ch3 edges of C_n. A two-line proof is available from the fact that deleting C leaves paths and an odd cycle forces some C-free path of length at least two. As a computational sanity check, enumerate all stable sets of C_7, C_9, and C_11 and confirm the stated path exists in every case; this would settle the only non-obvious combinatorial assertion used in the antihole case.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No significant objection identified. Theorem 1.4's proof is correct in substance. Two steps are compressed but repairable. First, C_A = (A1∩C)∪(A2∩C) is not literally a clique cutset of G[A] when one of A1\\C or A2\\C is empty; however, the needed conclusion that an induced odd hole or antihole H cannot contain vertices in both V1 and V2 is then automatic because the missing side contributes no vertices to G[A]. Second, the odd-antihole case asserts without proof that in the odd cycle H̄, with C a stable set, there exist h1,h2,h3 outside C and c in C with edges h1h2, h2c, ch3. This claim is true: deleting C from an odd cycle leaves at least one path of length at least two, and taking c adjacent to that path gives the required configuration. Lemma 1.1 is a standard theorem and applies to odd holes and odd antiholes, since both are minimal imperfect; citing Golumbic is sufficient. The remaining reasoning, including the P5 constructions in both the hole and antihole cases, checks out.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":5893,"tokens_out":17642,"duration_ms":192466,"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.","major_comments":[],"minor_comments":[{"comment":"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":"Section 2, proof of Theorem 1.4"},{"comment":"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":"Section 2, odd antihole case in Theorem 1.4"},{"comment":"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":"Section 2, proof of Lemma 2.3"},{"comment":"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":"Section 2, Lemmas 2.1 and 2.2"},{"comment":"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.","section":"Section 3, proof of Theorem 3.2"},{"comment":"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.","section":"References and Figure 1"}],"recommendation":"minor_revision","confidential_remarks":"The paper is competent and the main theorem is correct in substance after small clarifications. The criticism of [7] is fair and appropriately documented. No concerns about novelty or scope for a combinatorics journal."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThe short version: Theorem 1.4 is real. I checked the proof and it holds; the two spots that look compressed are both easily patched. The paper deserves a serious referee.\n\nThe genuinely new result is that a P5-free minimally non-perfectly divisible graph cannot contain a clique cutset. That is the first nontrivial confirmation of Conjecture 1.2 for P5-free graphs, and it rescues the Dong–Xu–Yu theorem on (P5,C5,K2,3)-free graphs by replacing their flawed proof. The counterexample to their Lemma 2.3 looks correct. The NP-hardness reduction via triangle-free graphs is clean: for triangle-free G, perfect divisibility is equivalent to 3-colorability, so recognition is NP-hard.\n\nThe paper gets terse in two places in Theorem 1.4. First, C_A is not literally a clique cutset of G[A] when one side of the separation is empty. But then the needed conclusion—that an induced odd hole or antihole cannot meet both sides—is automatic, so the argument survives with a one-line fix. Second, the odd-antihole case asserts an existence claim about the complementary cycle without proof. The claim is correct: for any c in C, its two neighbors on the cycle plus one more neighbor give the required configuration. The stress-test note covers both points and I agree with it. Lemma 2.3 is also a bit quick about why G[A] is perfect, but the clique-cutset argument via Lemma 1.1 is standard.\n\nNo data, no parameter fitting, no circularity. The citation pattern is fine; self-citations are relevant and not excessive.\n\nI recommend accepting after a minor revision that expands those two terse steps. The paper is for graph theorists working on perfect divisibility and P5-free coloring. It deserves a serious referee and likely quick acceptance. I would cite it if I worked in the area.","headline":"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.","tokens_in":6432,"tokens_out":13375,"would_cite":true,"duration_ms":143236,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15","05C69","05C75"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["perfectly divisible graphs","minimally non-perfectly-divisible graphs","clique cutset","P5-free graphs","4K1-free graphs","NP-hard recognition","perfect graphs","chromatic number"],"falsifier":"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.","tokens_in":5472,"feed_emoji":"🧩","tokens_out":7391,"duration_ms":177206,"temperature":0.7,"pith_summary":"A graph is perfectly divisible when every induced subgraph has a set of vertices that meets all its largest cliques and induces a perfect graph; a minimally non-perfectly-divisible (MNPD) graph is a smallest counterexample to this property. The paper's central result is that a P5-free MNPD graph—where P5 is the path on five vertices—cannot contain a clique cutset, a vertex set whose removal disconnects the graph. Proving this closes a gap left by an earlier incorrect proof and re-establishes that (P5, C5, K2,3)-free graphs are perfectly divisible. The paper also shows that recognizing perfectly divisible graphs is NP-hard: for triangle-free graphs, perfect divisibility is exactly 3-colorability. This matters because clique cutsets are the standard decomposition tool, and knowing that minimal counterexamples cannot have them turns perfect divisibility of P5-free classes into a structural check on the remaining cutset-free graphs.","feed_headline":"P5-free minimal counterexamples have no clique cutsets","feed_subtitle":"Theorem restores perfect divisibility for (P5,C5,K2,3)-free graphs and shows recognition is NP-hard.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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$."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the folklore Lemma 1.1, that no minimal imperfect graph contains a clique cutset, on which the fusion argument relies.","marker":"[9]"},{"why":"Provides the Strong Perfect Graph Theorem, used to identify an imperfect $G[A]$ with an odd hole or odd antihole.","marker":"[3]"},{"why":"The earlier proof of perfect divisibility of $(P_5,C_5,K_{2,3})$-free graphs whose incorrect Lemma 2.3 this paper repairs.","marker":"[7]"},{"why":"Introduces perfectly divisible graphs and the good-partition definition the proof works with.","marker":"[10]"},{"why":"Shows 3-colorability of triangle-free graphs is NP-hard, the baseline for the reduction in Theorem 3.2.","marker":"[15]"}],"fun_headline_variants":["P5-free MNPD graphs have no clique cutsets","Recognition of perfectly divisible graphs is NP-hard","Clique cutsets absent in P5-free minimally non-perfectly divisible graphs","P5-free and 4K1-free MNPD graphs lack clique cutsets"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["P5-free MNPD graphs have no clique cutsets","Recognition of perfectly divisible graphs is NP-hard","Clique cutsets absent in P5-free minimally non-perfectly divisible graphs","P5-free and 4K1-free MNPD graphs lack clique cutsets"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000967,"raw_usage":{"total_tokens":4150,"prompt_tokens":1020,"completion_tokens":3130,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":636,"completion_tokens_details":{"reasoning_tokens":3055}},"tokens_in":636,"tokens_out":3130,"duration_ms":28017,"temperature":1.0,"reasoning_tokens":3055,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T00:48:09.457919+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the folklore Lemma 1.1, that no minimal imperfect graph contains a clique cutset, on which the fusion argument relies."},{"cited_title":"Chudnovsky, N","cited_arxiv_id":null,"evidence_quote":"Provides the Strong Perfect Graph Theorem, used to identify an imperfect $G[A]$ with an odd hole or odd antihole."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces perfectly divisible graphs and the good-partition definition the proof works with."},{"cited_title":"Maffray, M","cited_arxiv_id":null,"evidence_quote":"Shows 3-colorability of triangle-free graphs is NP-hard, the baseline for the reduction in Theorem 3.2."}],"review_version":1}