The chromatic number of ($P_{5}, K_{5}-e$)-free graphs

Yian Xu

Published 2022-10-10, updated 2023-04-10Version 2

Let $G$ be a graph. We use $\chi(G)$ and $\omega(G)$ to denote the chromatic number and clique number of $G$ respectively. A $P_5$ is a path on 5 vertices. A family of graphs $\mathcal{G}$ is said to be {\it$\chi$-bounded} if there exists some function $f$ such that $\chi(G)\leq f(\omega(G))$ for every $G\in\mathcal{G}$. In this paper, we show that the family of $(P_5, K_5-e)$-free graphs is $\chi$-bounded by a linear function: $\chi(G)\leq \max\{13,\omega(G)+1\}$.