{"id":"fcb5bbd5-39cb-42c9-bb42-ef6d4876c30e","arxiv_id":"2509.01698","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For (bull,claw)-, (bull,chair,C5)-, and (bull,claw,C5)-free graphs, the paper lists all structures that force chromatic number above 4 or 5, and gives a k-colorability criterion for clique expansions of odd cycles.","lead":"Colorability with four or five colors is fully described for several graph families that forbid the small bull shape together with claws or chairs: every non-4-colorable example must contain one of a short list of special subgraphs. A separate theorem gives an exact condition for k-coloring any odd cycle whose vertices are expanded into cliques.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Exceptional graphs named C_p⊕K_j use C_p for an antihole while the paper defines C_p as a cycle; as literally stated, the main dichotomy theorems are false.","rationale":"The reader's weakest assumption exactly identifies the same load-bearing concern: the exception names in the main theorems are written with C_p but the proofs require \\overline{C_p}. This is not a peripheral ambiguity. In the proof of Theorem 6, after finding an odd antihole Q and a vertex w with N_Q(w)=Q, the paper says the graph contains C7⊕K1; the graph actually contains \\overline{C7}⊕K1. The same substitution is required for Theorem 7(ii) and Theorem 8(ii)–(iii). The distinction is mathematically substantial: a cycle joined with K1 is 4-colorable and claw-containing, while the antihole joined with K1 is 5-chromatic and, for p=7, (bull,claw)-free. Thus the stated theorems fail under the paper's own definitions unless C_p in exceptions is redefined as the antihole. Because the three main characterizations are precisely lists of these exceptional graphs, the notation is load-bearing. I do not see a separate more severe flaw after mentally testing the core Theorem 4; its condition matches the known weighted-coloring formula for odd cycles. However, the proof is abbreviated and several facts (e.g., Fact 18, Fact 23) are asserted without proof, so conditional acceptance is appropriate. The reader's verdict should remain CONDITIONAL until the notation is corrected and the skipped details are supplied. I agree with the reader's assessment and recommend no change to the verdict.","tokens_in":9953,"tokens_out":26115,"duration_ms":288506,"concrete_test":"Implement the graph G = \\overline{C7} ⊕ K1 in a graph library (e.g., NetworkX). Verify (a) χ(G)=5 via an exact coloring solver; (b) G is bull-free and claw-free by exhaustive induced-subgraph checks; (c) G contains no induced subgraph isomorphic to any of the literal exceptions, especially C7⊕K1 (wheel W7), C5⊕K2, K5, M7⊕K1, or the listed clique expansions. If all three checks pass, Theorem 6 as literally written is refuted. Then rerun the same check with item (i) replaced by \\overline{C7}⊕K1 and confirm consistency. Repeat for \\overline{C9}⊕K1 to test Theorem 8(iii).","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorems 6–8 state their exceptions using 'C7⊕K1', 'C2i+1⊕K2', and 'C9⊕K1', but Section 1 unambiguously defines C_p as an induced cycle. In the proofs, these graphs arise from a vertex adjacent to all vertices of an odd antihole Q (Section 5.2, Section 7.2), so the intended graph is the join of the antihole, not the cycle, with K_j. The distinction is not cosmetic: C7⊕K1 as a cycle is the wheel W7, which is 4-colorable and contains a claw, so it cannot be the non-4-colorable (bull,claw)-free exception named in Theorem 6(i). The intended graph, \\overline{C7}⊕K1, is (bull,claw)-free with χ=5. Under the paper's literal notation, this graph is not covered by any item of Theorem 6: it does not contain W7, C5⊕K2, K5, M7⊕K1, the listed clique expansions, or an induced C5 with more than 8 vertices. The analogous issue affects Theorem 8(iii) with C9⊕K1, where the cycle join has χ=4 and cannot be an obstruction to 5-colorability. Because the three main characterizations depend exactly on these exception names, the theorem statements as written are false; they become plausible only after silently switching C_p to mean \\overline{C_p} in exceptional graphs. This is a load-bearing notational inconsistency, not a mere typo, and it should be fixed and verified explicitly.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies k-colorability of graphs that are bull-free and additionally claw-free or chair-free. Its main results are: Theorem 4, a necessary and sufficient criterion for k-colorability of a clique expansion of an odd cycle (consecutive clique sizes sum at most k and total size at most nk); Theorems 6 and 7, structural dichotomies for non-4-colorable connected (bull,claw)-free and (bull,chair,C5)-free graphs; and Theorem 8, a dichotomy for non-5-colorable connected (bull,claw,C5)-free graphs. The proofs use the Strong Perfect Graph Theorem, structure theorems for (bull,claw)-free graphs from [4], and local arguments about neighborhoods of an odd hole or antihole, with some reliance on unpublished manuscripts [5], [11], [12].","tokens_in":10319,"tokens_out":11135,"duration_ms":125393,"significance":"If established, these results are substantial: Theorem 4 provides a clean, falsifiable criterion for all clique expansions of odd cycles, and Theorems 6 and 8 would give complete obstruction lists for 4- and 5-colorability in structured hereditary classes, with potential consequences for coloring algorithms. The paper is well organized and the overall strategy is plausible. However, as written, the statements are not reliable because of a load-bearing notational inconsistency, and several proof steps are only sketched. The results do not yet meet the standard of a fully verified characterization.","major_comments":[{"comment":"The definition of C_p as an induced cycle is inconsistent with its use in the main theorems. In §5.2, Q is an odd antihole; when a vertex dominates Q, the paper says the exceptional graph is C7⊕K1. Literally, C7⊕K1 is the wheel W7, which contains a claw and is 4-colorable, so it cannot be the non-4-colorable (bull,claw)-free obstruction. The intended graph is \\overline{C7}⊕K1. The same issue affects Theorem 8(iii) (C9⊕K1) and Theorem 7(i). In contrast, Theorem 7(ii) is generated from an actual induced cycle in §6.2, so a global redefinition of C_p as antihole would also be wrong. Thus the three main dichotomy theorems, as stated, have no consistent reading under which they are true. This is load-bearing and must be fixed by introducing \\overline{C_p} (or equivalent notation) and re-verifying each occurrence.","section":"Section 1 and Sections 5.2, 6.1, 7.2"},{"comment":"Fact 18 is stated without proof: it asserts that if w,w' are adjacent to an odd antihole Q and N(w)∪N(w')≠Q, then ww' is an edge. This fact is used in the p=7 case to force K5 or the clique expansion C[1,3,1,3,1], and again in the p=5 case. Since this inference is load-bearing for Theorem 6, a proof or citation must be supplied.","section":"Section 5.2, Fact 18"},{"comment":"The sufficiency direction of Theorem 4 is not actually proved. The text says 'It is easy to show' and describes a coloring after finding an index l, but the existence of l is asserted without a rigorous argument, and the coloring of the intervening cliques is not fully specified. Condition (i) is not visibly used in the sufficiency argument. Since Theorem 4 is used to derive Corollary 5 and Theorem 8(vi), a complete proof is needed.","section":"Section 4, proof of Theorem 4"},{"comment":"Fact 23 (H is complete) is only a short sketch. The steps 'Then w3∈C' and 'Since Δ(G)≤8, we may assume w1w3∉E(G)' are not justified. This fact is used to reduce the 10-vertex case in Theorem 8, so these gaps need to be filled.","section":"Section 7.2, Fact 23"}],"minor_comments":[{"comment":"The phrase 'all indices are taken modulo k' should refer to the cycle length (2n+1 or p), not the number of colors k.","section":"Theorem 4 and Corollary 5"},{"comment":"Typos: 'without loosing generality' should be 'without losing generality'; also 'F act' appears in Section 5.2.","section":"Introduction and Section 4"},{"comment":"The sentence 'Suppose that Q ̸= C5 = C5' is nonsensical; it should be something like 'Suppose Q is not isomorphic to C5'.","section":"Lemma 16"},{"comment":"In the proof of Fact 19, the case ℓ=2 says the set {v_{k-1}, v_k, w, v_{k+1}, v_{k+2}} induces a bull. The notation and the argument for why this is a bull should be made explicit, especially since the figure reference is not fully self-contained.","section":"Fact 19 proof"},{"comment":"After fixing the C_p notation, the isomorphisms 'G ∼= C9⊕K1' and 'G ∼= C7⊕K2' in the proof of Theorem 8 need to be updated consistently (e.g., to \\overline{C9}⊕K1 and \\overline{C7}⊕K2).","section":"Section 7.2"}],"recommendation":"major_revision","confidential_remarks":"The notation problem is more than a typo: no single interpretation of C_p makes Theorems 6–8 all true, so the statements need a substantive correction, not just a local edit. Additionally, the heavy reliance on unpublished self-cited manuscripts [5], [11], and [12], especially Theorem 3 from [12] in the proof of Theorem 7, may be a verification barrier for the editor. I did not see evidence that the central results are unsalvageable; the intended statements are plausible, but the current manuscript does not establish them."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The thing to know about this paper is that it has a genuinely useful new result and a load-bearing notation bug. Theorem 4, the criterion for k-colorability of clique expansions of odd cycles, looks new and is the cleanest part. The 4- and 5-colorability dichotomies for (bull,claw)-free and related classes are also new extensions beyond the earlier 3-color results, and the overall strategy — use the Strong Perfect Graph Theorem, then split into odd-hole/odd-antihole cases — is sound.\n\nBut the theorems as stated are false. The paper defines C_p as an induced cycle, yet uses C7⊕K1 and C9⊕K1 in the exception lists to name what are actually joins of odd antiholes with K_j. Under the literal definition, C7⊕K1 is the wheel W7, which is 4-colorable and contains a claw, so it cannot be the non-4-colorable (bull,claw)-free exception in Theorem 6. The same problem hits Theorem 8(iii). The stress-test's example is exact: the intended graph \\overline{C7}⊕K1 has chromatic number 5 and is (bull,claw)-free, and it isn't covered by any other item of Theorem 6. So the main dichotomy theorems are not merely imprecisely written; they are wrong as printed.\n\nThere are also smaller issues. Fact 18 and Fact 23 are given with only a one-line justification, and the sufficiency direction of Theorem 4 is argued in a paragraph and a half — all three need real proofs for a referee to check. The paper leans heavily on unpublished self-cited manuscripts [5], [11], [12], which is a burden, though not disqualifying if those manuscripts are made available.\n\nWhat's good: the ideas are right. The structural lemmas (Fact 19–21 in the (bull,chair)-free case, the clique-expansion reduction) point to a correct proof once the notation is fixed. I suspect the paper is salvageable with a careful revision: change C_p to \\overline{C_p} in the exception names, add the missing proof details, and make the dependence on the unpublished papers explicit.\n\nFor a referee: yes, this deserves serious refereeing, but not acceptance in its current form. I'd ask for major revision. It's the kind of paper I'd bring up in reading group to talk about how notation can silently invert a theorem.","headline":"Real new results, but the main theorems are false as written because C_p⊕K_j silently means the join of an odd antihole, not a cycle.","tokens_in":10833,"tokens_out":4725,"would_cite":false,"duration_ms":48516,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15","05C17","68Q25","68W40"],"pacs":[],"model":"deepseek-v4-flash","headline":"Odd-cycle clique expansions are k-colorable exactly when two simple size inequalities hold, and this yields complete classifications of all non-4- and non-5-colorable graphs in several bull-free families.","keywords":["4-colorability","5-colorability","bull-free graphs","claw-free graphs","clique expansion of odd cycles","forbidden induced subgraphs","perfect graphs","chromatic number"],"falsifier":"Decide the convention for C7 in the exception list of Theorem 6. If C7 means the ordinary 7-cycle, then the graph made by joining a single new vertex to every vertex of the complement of a 7-cycle is a 5-chromatic (bull,claw)-free graph not on the list, so the exception list would be incomplete; if C7 means the complement of the 7-cycle, the listed graph is exactly that obstruction. Checking which graph a 4-colorability solver computes as 5-chromatic settles which reading the theorem requires.","tokens_in":9864,"feed_emoji":"🎨","tokens_out":10646,"duration_ms":108815,"temperature":0.7,"pith_summary":"This paper gives a complete arithmetic test for coloring \"clique expansions\" of odd cycles: replace each vertex of an odd cycle by a clique, joining consecutive cliques completely. For such a graph, k-colorability holds exactly when every pair of neighboring cliques has at most k vertices total and the whole graph has at most nk vertices, where the cycle has 2n+1 positions. Using that test, the authors classify every connected graph that contains no bull (a triangle with two pendant edges) and no claw (three leaves joined to one center) and is not 4-colorable: it must contain one of a short list of explicit induced subgraphs. Analogous complete dichotomies are proved for non-4-colorable (bull, chair, C5)-free graphs and for non-5-colorable (bull, claw, C5)-free graphs, where the chair is a claw with one leg subdivided. The upshot is that in these families, deciding k-colorability reduces to checking a finite list of named obstructions.","feed_headline":"Two inequalities settle when blown-up odd cycles are k-colorable","feed_subtitle":"The same two-count test yields complete obstruction lists for 4- and 5-colorability in key bull-free graph families.","key_machinery":"The central object is the clique expansion C_p[k_1,...,k_p]—a cycle whose vertices are replaced by cliques of specified sizes, with all edges between consecutive cliques. The load-bearing identity is the pair of inequalities in Theorem 4, which turn k-colorability into arithmetic. Around it, the proofs rely on the Strong Perfect Graph Theorem to split non-perfect graphs into odd-hole and odd-antihole cases; on structural facts (Lemma 14, Lemma 15, Fact 19) describing how a vertex outside an odd antihole or odd cycle can attach to it without creating a bull, claw, or chair; and on the identity χ(G)=n−β0(G) for graphs with independence number 2, which controls the 5-colorability cases.","core_discovery":"At the core is Theorem 4: a clique expansion C_{2n+1}[k_1,...,k_{2n+1}] is k-colorable exactly when k_i+k_{i+1}≤k for every i and the sum of the k_i is at most nk. The two inequalities are necessary by a color-repetition count around the cycle and sufficient by the circular k-coloring algorithm. The dichotomy theorems (Theorems 6–8) then use the Strong Perfect Graph Theorem and structural lemmas to reduce any non-perfect (bull,claw)-free graph either to such a clique expansion or to an odd antihole with tightly constrained outside attachment; each case leads to one of the listed exceptional subgraphs.","pith_inferences":["The paper leaves implicit that Theorem 4 gives a polynomial-time decision procedure for k-colorability of odd-cycle clique expansions, since the two inequalities can be checked in time linear in the number of cliques.","The same total-vertex-count condition looks like a prototype for k-colorability of clique expansions of other base graphs: the local condition controls adjacent cliques, and the global condition controls how colors wrap around a cycle.","Because the exception lists in Theorems 6 and 8 are all small gadgets joined to a large clique or cycle, an algorithmic recognizer for these classes could test non-colorability by checking induced subgraphs up to a fixed size rather than solving a general coloring instance."],"forward_implications":["For any clique expansion of an odd cycle, checking k-colorability requires no search: just verify the two inequalities.","Every connected (bull,claw)-free graph that is not 4-colorable contains one of the listed induced subgraphs, so the obstructions give a finite certificate for non-4-colorability in this class.","Every connected (bull,claw,C5)-free graph that is not 5-colorable is either large with independence number 2, has a vertex of degree at least 9, or contains one of the listed clique/cycle obstructions; otherwise it is 5-colorable.","Corollary 5 extends the 3-colorability dichotomies from earlier work to arbitrary k for (bull,claw)-free graphs with an induced cycle of length at least 7 and independence number at least 3."],"supporting_citations":[{"why":"Supplies Theorem 10 and Theorem 11, which reduce connected (bull,claw)-free graphs with independence number at least 3 to clique expansions of odd cycles.","marker":"[4]"},{"why":"The Strong Perfect Graph Theorem: a perfect graph has chromatic number equal to clique number, so non-perfect graphs must contain an odd hole or odd antihole, which organizes the proofs of Theorems 6–8.","marker":"[9]"},{"why":"Prior dichotomy for (bull,claw)-free graphs (3-colorable, or contains W5, or contains a spindle M_{3i+1}) that motivates and is extended here; also gives Proposition 1 that spindles are not 3-colorable.","marker":"[5]"},{"why":"Theorem 3: (bull,chair)-free graphs are 3-colorable unless they contain an odd wheel or a spindle, used in the proof of Theorem 7.","marker":"[12]"},{"why":"Lemma 12: a claw-free graph with independence number at least 3 and an odd antihole contains an induced C5, used to force independence number 2 in the antihole case.","marker":"[1]"},{"why":"Structural analysis of (bull,chair)-free graphs around cycles, used in Fact 19 to describe the possible neighborhoods of outside vertices.","marker":"[11]"}],"fun_headline_variants":["Two inequalities fully decide k-colorability of odd cycle blow-ups","Bull-free graphs: exact 4- and 5-colorability obstruction lists","Blown-up odd cycles: k-colorable iff two counts hold","Complete k-coloring test for clique expansions of odd cycles","Dichotomy theorems for bull-free graphs: 4- and 5-colorability"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The exception lists in Theorems 6–8 use C7 to mean the complement of a 7-cycle (a graph whose non-edges form a 7-cycle), not the ordinary cycle itself; all the classification proofs rely on that convention.","fun_headline_variants_meta":{"raw":{"variants":["Two inequalities fully decide k-colorability of odd cycle blow-ups","Bull-free graphs: exact 4- and 5-colorability obstruction lists","Blown-up odd cycles: k-colorable iff two counts hold","Complete k-coloring test for clique expansions of odd cycles","Dichotomy theorems for bull-free graphs: 4- and 5-colorability"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000223,"raw_usage":{"total_tokens":1255,"prompt_tokens":669,"completion_tokens":586,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":413,"completion_tokens_details":{"reasoning_tokens":492}},"tokens_in":413,"tokens_out":586,"duration_ms":7133,"temperature":1.0,"reasoning_tokens":492,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T12:19:33.326714+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Decide the convention for C7 in the exception list of Theorem 6. If C7 means the ordinary 7-cycle, then the graph made by joining a single new vertex to every vertex of the complement of a 7-cycle is a 5-chromatic (bull,claw)-free graph not on the list, so the exception list would be incomplete; if C7 means the complement of the 7-cycle, the listed graph is exactly that obstruction. Checking which graph a 4-colorability solver computes as 5-chromatic settles which reading the theorem requires.","supporting_citations":[{"cited_title":"Brause, P","cited_arxiv_id":null,"evidence_quote":"Supplies Theorem 10 and Theorem 11, which reduce connected (bull,claw)-free graphs with independence number at least 3 to clique expansions of odd cycles."},{"cited_title":"Chudnovsky, N","cited_arxiv_id":null,"evidence_quote":"The Strong Perfect Graph Theorem: a perfect graph has chromatic number equal to clique number, so non-perfect graphs must contain an odd hole or odd antihole, which organizes the proofs of Theorems 6–8."},{"cited_title":"Brause, P","cited_arxiv_id":null,"evidence_quote":"Prior dichotomy for (bull,claw)-free graphs (3-colorable, or contains W5, or contains a spindle M_{3i+1}) that motivates and is extended here; also gives Proposition 1 that spindles are not 3-colorable."},{"cited_title":"On the distinguishing chromatic number in hereditary graph classes","cited_arxiv_id":"2505.17193","evidence_quote":"Theorem 3: (bull,chair)-free graphs are 3-colorable unless they contain an odd wheel or a spindle, used in the proof of Theorem 7."},{"cited_title":"Ben Rebea: Étude des stables dans les graphes quasi-adjoints (Thèse) Université de Grenoble, France (1981)","cited_arxiv_id":null,"evidence_quote":"Lemma 12: a claw-free graph with independence number at least 3 and an odd antihole contains an induced C5, used to force independence number 2 in the antihole case."}],"review_version":1}