A tight linear bound to the chromatic number of $(P_5,K_1+(K_1\cup K_3))$-free graphs

Abstract

Let $F_1$ and $F_2$ be two disjoint graphs. The union $F_1\cup F_2$ is a graph with vertex set $V(F_1)\cup V(F_2)$ and edge set $E(F_1)\cup E(F_2)$, and the join $F_1+F_2$ is a graph with vertex set $V(F_1)\cup V(F_2)$ and edge set $E(F_1)\cup E(F_2)\cup \{xy\;|\; x\in V(F_1)\mbox{ and } y\in V(F_2)\}$. In this paper, we present a characterization to $(P_5,K_1\cup K_3)$-free graphs, prove that $\chi (G)\le 2\omega (G)-1$ if $G$ is $(P_5,K_1\cup K_3)$-free. Based on this result, we further prove that $\chi (G)\le$max$\{2\omega (G),15\}$ if $G$ is a $(P_5,K_1+(K_1\cup K_3))$-free graph, and construct an infinite family of $(P_5,K_1+(K_1\cup K_3))$-free graphs such that every graph $G$ in the family satisfies $\chi (G)=2\omega (G)$.

arXiv admin note: text overlap with arXiv:2202.13177