Optimal chromatic bound for ($P_3\cup P_2$, house)-free graphs

Abstract

Let $G$ and $H$ be two vertex disjoint graphs. The {\em union} $G\cup H$ is the graph with $V(G\cup H)=V(G)\cup V(H)$ and $E(G\cup H)=E(G)\cup E(H)$. We use $P_k$ to denote a {\em path} on $k$ vertices, use {\em house} to denote the complement of $P_5$. In this paper, we show that $\chi (G)\le 2\omega (G)$ if $G$ is ($P_3\cup P_2$, house)-free. Moreover, this bound is optimal when $\omega (G)\ge 2$.

arXiv admin note: text overlap with arXiv:2307.11946