{"id":"arxiv/2607.27850","url":"https://arxiv.org/abs/2607.27850","tags":["math.CO"],"score":0,"title":"Optimal binding function for (cap,even hole)-free graphs with no short odd holes","domain":"math.CO","source":"arxiv","authors":["Chenglong Deng","Xuding Zhu"],"reviews":0,"subject":"math.CO","summary":"A hole in a graph is an induced cycle of length at least $4$. A cap is a hole together with a vertex adjacent to exactly two consecutive vertices of it. Chen, Xu and Xu conjectured that if $q\\ge2$ and $G$ is a $(\\mathrm{cap},\\mathrm{even\\ hole})$-free graph with no odd hole of length at most $2q-1$, then $χ(G)\\le \\left\\lceil \\frac{2q+1}{2q}ω(G)\\right\\rceil.$ They confirmed the conjecture for $q \\le 3$. In this paper, we prove the conjecture for all $q \\ge 3$. As a corollary, we prove that for such a graph $G$, $χ_f(G)\\le \\frac{2q+1}{2q}ω(G).$","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-30","reactions":{}}