An improved polynomial $\chi$-bound for $\{P_5,C_5\}$-free graphs

Abstract

Nguyen~\cite{Nguyen2025} recently proved that every $\{P_5,C_5\}$-free graph $G$ satisfies $\chi (G)\le \omega (G{)}^{40}$. Building on his framework, we introduce two refinements, namely a sharper cutset decomposition using the $C_5$-free condition and an improved density-increment argument. These yield a polynomial $\chi$-binding function with exponent $24$, improving the previous bound of $40$.

arXiv comment15 pages, comments are welcome!