Optimal coloring of $\{\mathrm{cap},\mathrm{even}\mathrm{hole}\}$-free graphs with no short odd holes

Abstract

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}\mathrm{hole}\}$-free graph $G$ satisfies $\chi (G)\le \lceil \frac{5}{4}\omega (G)\rceil$, and improved this bound to $\chi (G)\le \lceil \frac{7}{6}\omega (G)\rceil$ when $5$-holes are also excluded. They asked whether, for every integer $q\ge 3$, every $\{\mathrm{cap},\mathrm{even}\mathrm{hole}\}$-free graph $G$ with no odd hole of length at most $2q-1$ satisfies $$\chi (G)\le \lceil \frac{2q+1}{2q}\omega (G)\rceil .$$ We answer this question affirmatively and show that the bound is sharp for every $q\ge 3$.