Optimal binding function for (cap,even hole)-free graphs with no short odd holes

Abstract

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\ge 2$ and $G$ is a $(\mathrm{cap},\mathrm{even}\mathrm{hole})$-free graph with no odd hole of length at most $2q-1$, then $\chi (G)\le \lceil \frac{2q+1}{2q}\omega (G)\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$, ${\chi }_f(G)\le \frac{2q+1}{2q}\omega (G).$