{"id":"7e9c3434-7d35-4089-af05-2d8e21b9bcee","arxiv_id":"2603.21538","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.5,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Bull-free graphs satisfy the five perfect-divisibility conjectures (P5-, odd/even-hole-, 4K1-, fork-free); (bull,H)-free classes for H in {house,hammer,diamond} are perfect-Pollyanna.","lead":"The paper proves five open conjectures on perfect divisibility hold when restricted to bull-free graphs, and shows that (bull, house/hammer/diamond)-free graphs are perfect-Pollyanna. This yields new infinite families of perfectly divisible graphs and partial progress on chi-boundedness questions.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The reader correctly isolates the Chudnovsky–Safra dichotomy as the single external pillar; once that lemma and the homogeneous-set prohibition are granted, every subsequent argument is a self-contained structural case analysis that produces either a good weight-partition or a forbidden induced subgraph. The three main theorems and the perfect-Pollyanna corollaries therefore stand or fall together with those two classical facts, both of which are standard and correctly applied. Residual risk is only the ordinary possibility of a missed configuration in a long case analysis—an inherent feature of the method, not a concrete flaw. Consequently the ACCEPT verdict with high confidence remains appropriate; no adjustment is warranted.","tokens_in":18741,"tokens_out":432,"duration_ms":4475,"concrete_test":"Independently re-derive the partition (A,B) of Claim 13–14 in the 4K1 case (Section 5) from the neighbourhood lists of Claims 2–12 without invoking the clique-blowup description of Claim 10; if G[A] fails to be perfect or a maximal clique of G[B] remains maximal in G, the case analysis for Theorem 4 collapses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claims rest on the standard MNWD template together with the Chudnovsky–Safra dichotomy (Lemma 2) and the absence of homogeneous sets (Lemma 1). Both are correctly cited and applied: Lemmas 5–6 correctly force every bull-free MNWD graph to be connected and locally perfect with every M(v) imperfect and free of large odd antiholes; the subsequent case analyses (odd-torch, even-hole/house/hammer, 4K1) then produce the required good partitions or contradictions. The perfect-Pollyanna statements follow immediately once every MNWD graph in the relevant classes is shown to be triangle-free (Theorems 7–8 and Lemma 10). No hidden assumption, circular citation, or missing configuration that would invalidate the strongest claim is visible.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper studies perfect divisibility (and the stronger perfect weight-divisibility) for bull-free graphs. It proves that every (bull, odd-torch)-free graph, every (bull, even-hole)-free graph and every (bull, 4K1)-free graph is perfectly weight-divisible (Theorems 2–4), so the five conjectures of Hoàng and of Karthick et al. hold when restricted to bull-free graphs. It further introduces the notion of a perfect-Pollyanna class and shows that the classes of (bull, H)-free graphs for H ∈ {house, hammer, diamond} are perfect-Pollyanna (Theorems 5–6). The arguments proceed by the standard minimal non-perfectly-weight-divisible (MNWD) template: Lemmas 1–2 (homogeneous-set freeness and the Chudnovsky–Safra dichotomy) force every bull-free MNWD graph to be connected and locally perfect with every M(v) imperfect and free of large odd antiholes; subsequent case analyses around odd holes then produce either a good partition or a forbidden induced subgraph. Corollaries recover earlier results of Chudnovsky–Sivaraman and Karthick et al. and yield new perfect-divisibility statements for several (bull, path/cycle)-free classes.","tokens_in":18923,"tokens_out":732,"duration_ms":6446,"significance":"The results give a uniform positive answer to five open conjectures inside the bull-free world and introduce a clean “perfect-Pollyanna” framework that reduces perfect divisibility of (bull, H)-free graphs to the triangle-free case. The proofs are self-contained once the Chudnovsky–Safra dichotomy and the Strong Perfect Graph Theorem are granted, and they systematically strengthen earlier partial results. The work therefore advances both the structural theory of bull-free graphs and the programme of identifying hereditary classes that are perfectly divisible.","major_comments":[],"minor_comments":[{"comment":"Title of the arXiv version (“Perfect divisibility of some bull-free graphs and its application”) differs slightly from the abstract title; unify for the final version.","section":null},{"comment":"Figure 1 caption and the list of forbidden subgraphs would benefit from a short explicit definition of “odd torch on a 5-hole” already in the introduction, rather than only in the figure.","section":null},{"comment":"In the proof of Lemma 5 the phrase “H = v1v2···vkv1 is an odd hole” is slightly confusing because H is introduced as an antihole; a parenthetical remark that the complement is the hole would help.","section":null},{"comment":"Claim numbering restarts in each section; a global numbering or section-prefixed labels would make cross-references easier.","section":null},{"comment":"A few typographical slips remain (e.g., “appli cation”, “fiv e”, “Ho` ang” spacing, “geneality”). A careful copy-edit will remove them.","section":null},{"comment":"The final open problems (Problems 1–2) are well-motivated; a one-sentence remark on why the diamond case of Theorem 7 does not immediately settle Problem 2 would be useful for the reader.","section":null}],"recommendation":"accept","confidential_remarks":"The manuscript is a solid, carefully written contribution that fits the journal’s scope. No novelty or citation concerns arose. The proofs are long but follow a standard template and appear free of load-bearing gaps; I see no reason to request further referee rounds."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This paper settles Hoàng’s four perfect-divisibility conjectures and the Karthick–Kaufmann–Sivaraman fork conjecture, all restricted to bull-free graphs, by proving the stronger statements that (bull, odd-torch)-free, (bull, even-hole)-free and (bull, 4K1)-free graphs are perfectly weight-divisible. It also defines perfect-Pollyanna classes and shows that (bull, house)-, (bull, hammer)- and (bull, diamond)-free graphs are perfect-Pollyanna, which immediately yields three concrete path-plus-short-cycle corollaries.\n\nWhat is new is the single forbidden subgraph “odd torch” that simultaneously generalises the earlier Chudnovsky–Sivaraman (bull+odd-hole, bull+P5) and Karthick et al. (bull+fork) theorems, plus the perfect-Pollyanna notion itself. The technical work is the usual MNWD minimal-counterexample analysis: they invoke the Chudnovsky–Safra dichotomy (every bull-free graph has a homogeneous set or is locally perfect) together with the absence of homogeneous sets in MNWD graphs, force every such counterexample to be connected and locally perfect with every M(v) imperfect and free of large odd antiholes, then run case analyses around odd holes (or 5-holes when 4K1-free). The partitions constructed in Sections 3–5 look correct on a careful reading; the stress-test found no missing configuration or circular citation.\n\nSoft spots are the ordinary ones for this style of paper: the case distinctions are long, and absolute certainty that every subcase is covered rests on human inspection rather than machine checking. The reliance on the Chudnovsky–Safra lemma is explicit and correctly applied, not a hidden assumption. Citation pattern is clean and the Strong Perfect Graph Theorem is used only where expected.\n\nThis is for structural graph theorists working on χ-boundedness and perfect divisibility. It deserves a serious referee; the results are concrete, the proofs follow the accepted template of the field, and residual risk is the usual residual risk of long case analysis. I would send it out.","headline":"Solid case-analysis paper that settles five conjectures inside bull-free graphs and introduces a clean perfect-Pollyanna template; proofs look standard and careful.","tokens_in":19532,"tokens_out":541,"would_cite":true,"duration_ms":5494,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15","05C75"],"pacs":[],"model":"grok-4.5","headline":"Five open perfect-divisibility conjectures all hold for bull-free graphs, and three (bull, H)-free classes are perfect-Pollyanna.","keywords":["perfect divisibility","bull-free graphs","perfect-Pollyanna","odd torch","weight-divisible","homogeneous set","χ-boundedness"],"falsifier":"An explicit bull-free graph that is not perfectly divisible (or a bull-free minimal non-perfectly-weight-divisible graph that contains a triangle and no homogeneous set) would refute the main theorems.","tokens_in":19651,"feed_emoji":"▷","tokens_out":1041,"duration_ms":7922,"temperature":0.7,"pith_summary":"A graph is perfectly divisible when every induced subgraph can be split into a perfect piece and a leftover piece whose largest clique is strictly smaller. Five well-known conjectures assert that this property holds for P5-free graphs, odd-hole-free graphs, even-hole-free graphs, 4K1-free graphs, and fork-free graphs. The paper proves that every one of those five statements is true once the extra forbidden subgraph “bull” is added. The proofs proceed by showing that any minimal counter-example that is also bull-free must be triangle-free and therefore already known to be perfectly divisible. In addition, the authors introduce the notion of a perfect-Pollyanna class: a hereditary class C such that the intersection of C with any class whose triangle-free members are 3-colourable remains perfectly divisible. They prove that the three classes of (bull, house)-free, (bull, hammer)-free and (bull, diamond)-free graphs are perfect-Pollyanna, which immediately yields several new infinite families of perfectly divisible graphs.","feed_headline":"Five colouring conjectures hold for bull-free graphs","feed_subtitle":"Adding one forbidden subgraph settles Hoàng’s and Karthick’s perfect-divisibility questions","key_machinery":"The structural dichotomy for bull-free graphs: either a homogeneous set exists, or for every vertex v at least one of the neighbourhood N(v) or the non-neighbourhood M(v) induces a perfect graph. Combined with the fact that minimal non-perfectly-weight-divisible graphs have no homogeneous sets, this forces every candidate counter-example to be locally perfect and triangle-free, after which known colouring results finish the argument.","core_discovery":"Every (bull, odd-torch)-free graph, every (bull, even-hole)-free graph and every (bull, 4K1)-free graph is perfectly weight-divisible; consequently the five listed conjectures hold for bull-free graphs. Moreover the classes of (bull, H)-free graphs for H in {house, hammer, diamond} are perfect-Pollyanna.","pith_inferences":["The same dichotomy-plus-minimal-counterexample strategy may decide whether the whole class of bull-free graphs is perfect-Pollyanna, the open question left by the authors.","If every bull-free minimal non-perfectly-weight-divisible graph is forced to be triangle-free, the five conjectures would hold without any extra forbidden subgraphs.","The perfect-Pollyanna property supplies a uniform template for converting 3-colourability results on triangle-free graphs into perfect-divisibility theorems for larger hereditary classes."],"forward_implications":["All five open conjectures of Hoàng and Karthick et al. become true inside the bull-free world.","Any hereditary class whose triangle-free members are 3-colourable yields a perfectly divisible class when intersected with (bull, house)-, (bull, hammer)- or (bull, diamond)-free graphs.","Concrete new perfectly divisible families include (bull, P11, C4)-free, (bull, P14, C5, C4)-free and (bull, P17, C6, C5, C4)-free graphs.","Every (bull, odd-torch)-free or (bull, 4K1)-free graph satisfies χ ≤ ω(ω+1)/2."],"fun_headline_variants":["Bull-free graphs settle five perfect-divisibility conjectures","Perfect divisibility holds for all five bull-free conjectures","Bull-free graphs confirm Hoàng and Karthick perfect-divisibility claims","Five conjectures on perfect divisibility true in bull-free graphs","Bull-free graphs are perfect-Pollyanna for house hammer diamond"],"cache_read_input_tokens":16512,"weakest_assumption_plain":"The entire case analysis rests on the claim that every bull-free graph either has a homogeneous set or, for every vertex, at least one of its neighbourhood or non-neighbourhood induces a perfect graph.","fun_headline_variants_meta":{"raw":{"variants":["Bull-free graphs settle five perfect-divisibility conjectures","Perfect divisibility holds for all five bull-free conjectures","Bull-free graphs confirm Hoàng and Karthick perfect-divisibility claims","Five conjectures on perfect divisibility true in bull-free graphs","Bull-free graphs are perfect-Pollyanna for house hammer diamond"]},"model":"grok-4.5","effort":"low","cost_usd":0.005464,"raw_usage":{"total_tokens":1648,"prompt_tokens":1010,"num_sources_used":0,"completion_tokens":94,"cost_in_usd_ticks":54640000,"prompt_tokens_details":{"text_tokens":1010,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":544,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":1010,"tokens_out":94,"duration_ms":4835,"temperature":1.0,"reasoning_tokens":544,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-13T20:45:34.329404+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"An explicit bull-free graph that is not perfectly divisible (or a bull-free minimal non-perfectly-weight-divisible graph that contains a triangle and no homogeneous set) would refute the main theorems.","supporting_citations":[],"review_version":1}