{"id":"caf12fc7-7851-4ab3-9d88-2b9e53ea62c8","arxiv_id":"2506.19580","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Every (cap, even hole)-free graph G satisfies χ(G) ≤ ⌈5/4 ω(G)⌉, and every (cap, even hole, 5-hole)-free graph satisfies χ(G) ≤ ⌈7/6 ω(G)⌉, with both bounds attained by clique blowups of odd holes.","lead":"This paper proves the conjectured optimal chromatic bound for (cap, even hole)-free graphs: every such graph G satisfies χ(G) ≤ ⌈5/4 ω(G)⌉. It also proves a tighter bound for graphs that are additionally 5-hole-free, and both bounds are shown to be tight.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section 4.1 assumes, without proof or citation, the existence of a maximal triangle-free induced subgraph F of G with no clique cutset; this existence is needed to invoke Lemmas 2.1 and 2.2 and is the load-bearing entry point of both halves of Lemma 4.1.","rationale":"The reader identified Lemmas 2.1 and 2.2 as the weakest black-box assumptions. My reading agrees that these lemmas are central, but the sharper problem is an unproved existence assertion inside the proof of Lemma 4.1: the authors need a maximal triangle-free induced subgraph F that also has no clique cutset, and they do not justify that such an F exists. This is not covered by the statements of Lemmas 2.1 and 2.2, both of which are conditional on having such an F already. The rest of the argument, including the induction in Theorem 1.1 and the ceiling arithmetic around Section 3, appears internally coherent and I found no counterexample to the main theorem. The concern is therefore not a claim of falsehood; it is a missing load-bearing justification. The natural resolution is to supply or cite an existence proof, or to exhibit the required F by a short argument. Until then, acceptance should be conditional rather than unconditional.","tokens_in":16483,"tokens_out":43026,"duration_ms":442021,"concrete_test":"Check the cited source [2] for a lemma asserting that a (cap, even hole)-free graph with no clique cutset and with an odd hole has a maximal triangle-free induced subgraph with no clique cutset. If no such lemma is present, run a computational search over all (cap, even hole)-free graphs with n ≤ 12, no clique cutset, and at least one odd hole, testing whether each has at least one maximal triangle-free induced subgraph with no clique cutset. A counterexample would invalidate the first step of Lemma 4.1; a proof or a confirmed search would show the concern does not land.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"In both the K5-free and the K13-free cases, the proof says 'we may choose a maximal triangle-free induced subgraph F of G which has no clique cutset' (Section 4.1). This is not derived. Lemma 2.2 is conditional: it applies only to an F that already has no clique cutset, and Lemma 2.1 has the same requirement. The minimality assumptions on G do not, by themselves, guarantee that such an F exists. It is conceivable that every maximal triangle-free induced subgraph of a (cap, even hole)-free graph with no clique cutset and an odd hole has a clique cutset; in that case the structural reduction in Section 4 cannot even start. The only way to justify the assertion would be a theorem in [2] or [10] that is not quoted at the point of use. Since the blowup structure, the good-ear decomposition, and the entire path-extension case analysis in Lemma 4.1 all depend on this chosen F, this unproved existence step is the most load-bearing premise in the paper.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies χ-binding functions for (cap, even hole)-free graphs. It first proves a reduction theorem (Theorem 1.1) for clique blowups of a triangle-free graph F: with p>2q, proving χ(G)≤⌈p/(2q)ω(G)⌉ for all clique blowups of F is reduced to proving it only for blowups with clique number at most max{2q(p−q−2)/(p−2q), 2q}. The proof is by induction and removes a set T of size q from each bag, decomposing the remainder into two anticomplete parts. The paper then invokes structural characterizations of (cap, even hole)-free graphs without clique cutsets as clique blowups of triangle-free graphs obtainable by good ear additions, and proves by a lengthy case analysis (Lemma 4.1) the required bound for small clique number: χ≤⌈5/4ω⌉ for K5-free graphs and χ≤⌈7/6ω⌉ for (5-hole,K13)-free graphs. Theorem 1.2 follows by combining these pieces, and both bounds are shown tight by clique blowups of 5- and 7-holes, answering a question of Cameron et al.","tokens_in":16630,"tokens_out":14121,"duration_ms":134975,"significance":"If correct, this settles an open problem and improves the previous best bound for (cap, even hole)-free graphs. The reduction Theorem 1.1 is a clean and potentially reusable tool; the numerical inequalities in its proof are sound, and the ceiling slack is used correctly. The examples attaining the bounds are simple and convincing. The main caveats are two load-bearing presentation and support issues: the statement of Theorem 1.1 is misquantified, and the existence of a maximal triangle-free induced subgraph without a clique cutset is asserted rather than proved or cited. Both are fixable without changing the main idea.","major_comments":[{"comment":"The quantification of G′ is not the one used in the proof. As written, the theorem fixes one G′ with ω(G′)≤max{2q(p−q−2)/(p−2q), 2q} and asserts an equivalence between 'for every clique blowup G' and 'χ(G′)≤⌈p/(2q)ω(G′)⌉'. For a single fixed G′, the right-hand side cannot control all unbounded blowups. The proof and the applications in Section 4 require the hypothesis that every clique blowup G′ with ω(G′)≤M satisfies the inequality. Please restate Theorem 1.1 as a reduction: if every bounded-clique-number blowup of F satisfies the bound, then every clique blowup of F satisfies the bound, with the converse being immediate.","section":"Theorem 1.1 and Abstract"},{"comment":"The proof asserts, without proof or citation, that one may choose a maximal triangle-free induced subgraph F of G with no clique cutset. This appears in the proof of Theorem 1.2 ('we may choose a maximal triangle-free induced subgraph F of G which has no clique cutset') and again in both halves of Lemma 4.1. Lemmas 2.1 and 2.2 apply only to an F that already has no clique cutset; minimality of G and the absence of clique cutsets in G do not by themselves imply such an F exists. This assertion is the entry point for both the blowup structure and the good-ear decomposition, and hence for the entire case analysis. Please either prove this assertion or cite the precise theorem in [2] or [10] that guarantees it. If it is a known result, it should be stated in Section 2.","section":"Section 4 and Section 4.1"}],"minor_comments":[{"comment":"Lemma 4.2 is quoted from the authors' own arXiv preprint [4]. Since it is used both in the base case of Lemma 4.1 and in establishing reachability of the bounds, please include a short proof in the paper or cite a published source.","section":"Lemma 4.2 and References"},{"comment":"In the displayed formula before coloring X_{2m2−2}, the indices X_{2m1−1} and X_{2m1−3} appear where X_{2m2−1} and X_{2m2−3} are clearly intended; this makes the estimate hard to follow.","section":"Claim 4.5"},{"comment":"The claim that V1\\T is a union of pairwise anticomplete cliques is compressed; spelling out why a vertex of F cannot be incident with two V1-edges using ω(G)≥2q+1 would improve readability.","section":"Section 3 and Section 4.1"},{"comment":"There are several typos, including 'maximal triangle-free induced subgraph graph' in Section 4.1 and 'for for each odd integer' in Claim 4.3. Proofreading is needed.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The quantifier issue in Theorem 1.1 appears to be a formulation error rather than a mathematical gap, and the proof can be read as the intended reduction theorem. The existence of F is the point that needs the most attention; if the authors can supply a precise reference or a short proof, I would be willing to endorse the result. The manuscript is appropriate for a combinatorics journal."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version. The paper settles the 2018 Cameron et al. question: every (cap, even hole)-free graph has χ(G) ≤ ⌈5/4 ω(G)⌉, and the bound is tight. It also gives a sharp ⌈7/6ω(G)⌉ bound for the 5-hole-free case. That is a genuine result, not an incremental step. The main new tool is Theorem 1.1, a reduction that says for clique blowups of a triangle-free graph you only need to check the bound at bounded clique number. That theorem is proved by a clean induction with a numerical inequality that checks out. The path-extension case analysis in Section 4 is long but I did not find an obvious error in the inequalities. So the paper has real content.\n\nThe soft spot is in Section 4.1, at the entry to both parts of Lemma 4.1. The proof says 'we may choose a maximal triangle-free induced subgraph F of G which has no clique cutset.' This is asserted, not proved. Lemma 2.2 is conditional on F already having no clique cutset, and Lemma 2.1 has the same requirement. The minimality assumptions on G do not obviously give you such an F; a maximal triangle-free induced subgraph of a graph with no clique cutset can in principle have a clique cutset, because vertices outside F can reconnect the components. If there is a theorem in [2] that guarantees existence, it is not quoted at the point of use. I don't have a counterexample, and the assertion may be true, but as written it is load-bearing. A referee should ask for a proof or a citation. This is patchable, not fatal.\n\nMinor: the abstract attributes the problem to [2] and Problem 1.1 attributes it to [3]; one of those is wrong.\n\nWho should read this: people in χ-boundedness and even-hole-free structure. The reduction theorem is reusable. I would send it to a serious referee, because the result is important and the gap looks repairable.","headline":"Solves a 2018 open problem with a reusable reduction theorem, but Section 4.1 has an unproved existence claim for F that needs a fix.","tokens_in":17256,"tokens_out":9011,"would_cite":false,"duration_ms":87819,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15","05C75"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every (cap, even hole)-free graph can be colored with at most 5/4 times its clique number; forbidding 5-holes lowers the multiplier to 7/6.","keywords":["cap","even hole","chromatic number","clique number","binding function","clique blowup","odd-signable graphs","path extension"],"falsifier":"Run an exact search over all (cap, even hole)-free graphs on up to fourteen vertices, computing $\\chi(G)$ and $\\omega(G)$; any output with $\\chi(G)>\\lceil\\frac{5}{4}\\omega(G)\\rceil$ would refute the main theorem. The known equality cases—uniformly blown-up 5-holes and 7-holes—should appear with equality, and a violation of the analogous small-clique condition in Theorem 1.1 could be checked directly by constructing a triangle-free $F$ and choosing bag sizes just above the stated threshold.","tokens_in":16203,"feed_emoji":"🎨","tokens_out":15831,"duration_ms":139751,"temperature":0.7,"pith_summary":"The paper proves a best-possible coloring bound for graphs containing neither a cap nor an even hole. A cap is a hole with one extra vertex adjacent to exactly two consecutive vertices of the hole; an even hole is an induced cycle of even length at least four. The main theorem states that every such graph $G$ satisfies $\\chi(G)\\le \\lceil\\frac{5}{4}\\omega(G)\\rceil$, and if $G$ also has no hole of length five, then $\\chi(G)\\le \\lceil\\frac{7}{6}\\omega(G)\\rceil$; both bounds are attained by specific clique blowups of a 5-hole and a 7-hole. These results settle a question posed in 2018 about the exact linear binding function for this hereditary class. The proof works through a general reduction, Theorem 1.1, which reduces checking a $p/(2q)$ chromatic bound for all clique blowups of a triangle-free graph to checking only blowups with bounded clique number.","feed_headline":"No caps, no even holes: the 5/4 coloring bound is exact","feed_subtitle":"With no cap and no even hole, χ(G) is at most 5/4 of ω(G); ban 5-holes and the ratio drops to 7/6.","key_machinery":"The engine of the proof is Theorem 1.1, a reduction principle for clique blowups. It says that to prove a bound of the form $\\chi(G)\\le \\lceil\\frac{p}{2q}\\omega(G)\\rceil$ for all clique blowups of a triangle-free graph $F$, it is enough to check the bound only on those blowups whose clique number is at most $\\max\\{\\frac{2q(p-q-2)}{p-2q},2q\\}$. The proof carves a small set $T$ of vertices out of each bag, splits the remainder into two parts $V_1$ and $V_2$ with controlled clique numbers, colors each part by induction, and recombines the colorings. To connect this to the target class, the paper uses two structural theorems as black boxes: Lemma 2.2, which expresses a (cap, 4-hole)-free graph with a hole and no clique cutset (a clique whose removal disconnects the graph) as a clique blowup of a maximal triangle-free induced subgraph together with a universal clique (a clique complete to the rest of the graph), and Lemma 2.1, which builds triangle-free odd-signable graphs from a hole by controlled ear additions called good ear additions. The base cases of small clique number are handled by a path-extension coloring technique, which greedily extends a partial coloring along blown-up paths.","core_discovery":"At the level of the paper's own claims, the central discovery is a reduction and two sharp bounds. Theorem 1.1 says that for positive integers $p>2q$ and any triangle-free graph $F$, the inequality $\\chi(G)\\le \\lceil\\frac{p}{2q}\\omega(G)\\rceil$ holds for every clique blowup $G$ of $F$ as soon as it holds for those blowups with clique number at most $\\max\\{\\frac{2q(p-q-2)}{p-2q},2q\\}$. The paper then proves, by induction and structural decomposition, that every (cap, even hole)-free graph satisfies $\\chi(G)\\le \\lceil\\frac{5}{4}\\omega(G)\\rceil$, answering a 2018 question in the affirmative, and that every such graph with no 5-hole satisfies $\\chi(G)\\le \\lceil\\frac{7}{6}\\omega(G)\\rceil$. Uniform clique blowups of a 5-hole and of a 7-hole show the constants cannot be lowered, so the binding functions are optimal.","pith_inferences":["The closing remark suggests the pattern continues: for graphs whose shortest odd hole has length at least $2q+1$, the conjectured bound is $\\chi\\le \\lceil\\frac{2q+1}{2q}\\omega\\rceil$; this paper settles the cases $q=2$ and $q=3$, so $q=4$ is the immediate next test.","Because Theorem 1.1 is stated for arbitrary triangle-free $F$, the same reduction could transfer coloring bounds between very different hereditary classes once a structural decomposition into clique blowups is known.","The path-extension coloring argument is constructive, so the proof likely gives an efficient coloring algorithm when the clique number is bounded, though the paper does not claim this."],"forward_implications":["Every (cap, even hole)-free graph can be colored with at most $\\frac{5}{4}$ of its clique number; this is the exact linear binding function for the class.","Adding the absence of 5-holes improves the guarantee to $\\frac{7}{6}$ of the clique number, also tight.","Theorem 1.1 reduces any $p/(2q)$ coloring bound for clique blowups of a triangle-free graph to the case of bounded clique number, which can make such bounds easier to verify.","The reachability examples mean no smaller multiplier of $\\omega$ can serve as a universal bound for either class."],"supporting_citations":[{"why":"Supplies Lemma 2.2, the structural decomposition of (cap, even hole)-free graphs into a clique blowup of a maximal triangle-free subgraph plus a universal clique.","marker":"[2]"},{"why":"Supplies Lemma 2.1, the characterization of triangle-free odd-signable graphs without clique cutsets as obtainable from a hole by good ear additions.","marker":"[10]"},{"why":"Provides Lemma 4.2 on the exact chromatic ratio of clique blowups of odd holes, which supplies the base case and the reachability examples.","marker":"[4]"},{"why":"Introduces the path-extension coloring technique used in the proof of Lemma 4.1 to extend partial colorings along blown-up paths.","marker":"[22]"},{"why":"Gives the previous best upper bound for (cap, even hole)-free graphs, the benchmark that the new 5/4 bound improves.","marker":"[23]"}],"fun_headline_variants":["Sharp 5/4 coloring bound for (cap, even hole)-free graphs","χ ≤ 5/4ω proven optimal for cap-free even-hole-free graphs","Exact coloring ratio: 5/4 without caps/even holes, 7/6 without 5-holes","Optimal binding functions for (cap, even hole)-free graphs","No caps, no even holes: χ/ω ≤ 5/4 is reachable"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the two structural classifications imported from earlier work—one describing triangle-free odd-signable graphs as built from a hole by controlled ear additions, the other describing (cap, even hole)-free graphs as clique blowups of such a triangle-free graph plus a universal clique—hold for every graph in the class; if either fails, the coloring bound is not established.","fun_headline_variants_meta":{"raw":{"variants":["Sharp 5/4 coloring bound for (cap, even hole)-free graphs","χ ≤ 5/4ω proven optimal for cap-free even-hole-free graphs","Exact coloring ratio: 5/4 without caps/even holes, 7/6 without 5-holes","Optimal binding functions for (cap, even hole)-free graphs","No caps, no even holes: χ/ω ≤ 5/4 is reachable"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000563,"raw_usage":{"total_tokens":2745,"prompt_tokens":1091,"completion_tokens":1654,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":707,"completion_tokens_details":{"reasoning_tokens":1541}},"tokens_in":707,"tokens_out":1654,"duration_ms":12516,"temperature":1.0,"reasoning_tokens":1541,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T18:31:13.289438+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run an exact search over all (cap, even hole)-free graphs on up to fourteen vertices, computing $\\chi(G)$ and $\\omega(G)$; any output with $\\chi(G)>\\lceil\\frac{5}{4}\\omega(G)\\rceil$ would refute the main theorem. The known equality cases—uniformly blown-up 5-holes and 7-holes—should appear with equality, and a violation of the analogous small-clique condition in Theorem 1.1 could be checked directly by constructing a triangle-free $F$ and choosing bag sizes just above the stated threshold.","supporting_citations":[{"cited_title":"Cameron, M","cited_arxiv_id":null,"evidence_quote":"Supplies Lemma 2.2, the structural decomposition of (cap, even hole)-free graphs into a clique blowup of a maximal triangle-free subgraph plus a universal clique."},{"cited_title":"Conforti, G","cited_arxiv_id":null,"evidence_quote":"Supplies Lemma 2.1, the characterization of triangle-free odd-signable graphs without clique cutsets as obtainable from a hole by good ear additions."},{"cited_title":"Nearly optimal coloring of some C4-free graphs","cited_arxiv_id":"2409.06944","evidence_quote":"Provides Lemma 4.2 on the exact chromatic ratio of clique blowups of odd holes, which supplies the base case and the reachability examples."},{"cited_title":"Wu and B","cited_arxiv_id":null,"evidence_quote":"Introduces the path-extension coloring technique used in the proof of Lemma 4.1 to extend partial colorings along blown-up paths."},{"cited_title":"Xu, A better upper bound on the chromatic number of (cap, even hole)-free graphs, Disc","cited_arxiv_id":null,"evidence_quote":"Gives the previous best upper bound for (cap, even hole)-free graphs, the benchmark that the new 5/4 bound improves."}],"review_version":2}