Improved chromatic bounds for ($P_2\cup P_3$)-free graphs

Abstract

Let $G$ be a $(P_2\cup P_3)$-free graph, and let $k=\ddot{I}‰(G)\ge 1$. We prove that \[ χ(G)\leq \binom{k+2}{3}-\binom{k-1}{2} =\frac{k^3+11k-6}{6}. \] The previously best-known general bound for this unrestricted graph class, due to Bharathi and Choudum, was $\ddot{I}‡(G)\le \left(\genfrac{}{}{0ex}{}{k+2}{3}\right)$. To the best of our knowledge, this is the first improvement of their bound that applies to all $(P_2\cup P_3)$-free graphs. For $k\ge 3$, our result improves their estimate by exactly $\left(\genfrac{}{}{0ex}{}{k-1}{2}\right)$ colours, replacing $(k^3+3k^2+2k)/6$ by $(k^3+11k-6)/6$, and thereby eliminates the quadratic term without imposing any additional forbidden induced subgraph.