{"id":"arxiv/2607.25396","url":"https://arxiv.org/abs/2607.25396","tags":["math.CO"],"score":0,"title":"Optimal coloring of $\\{\\mathrm{cap},\\mathrm{even\\ hole}\\}$-free graphs with no short odd holes","domain":"math.CO","source":"arxiv","authors":["Feng Liu","Shuang Sun","Yan Wang"],"reviews":0,"subject":"math.CO","summary":"A \\emph{hole} is an induced cycle of length at least four, and an \\emph{even hole} is a hole of even length. A \\emph{cap} is obtained from a hole by adding a vertex adjacent to exactly two consecutive vertices of the hole. Chen, Xu, and Xu proved that every $\\{\\mathrm{cap},\\mathrm{even\\ hole}\\}$-free graph $G$ satisfies $χ(G)\\leq \\left\\lceil\\frac{5}{4}ω(G)\\right\\rceil$, and improved this bound to $χ(G)\\leq \\left\\lceil\\frac{7}{6}ω(G)\\right\\rceil$ when $5$-holes are also excluded. They asked whether, for every integer $q\\geq3$, every $\\{\\mathrm{cap},\\mathrm{even\\ hole}\\}$-free graph $G$ with…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-28","reactions":{}}