Kaiyang Lan

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

Nguyen~\cite{Nguyen2025} recently proved that every $\{P_5,C_5\}$-free graph $G$ satisfies $\chi(G)\leq \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$.