On the chromatic number of some $P_5$-free graphs

Let $G$ be a graph. We say that $G$ is perfectly divisible if for each induced subgraph $H$ of $G$, $V(H)$ can be partitioned into $A$ and $B$ such that $H[A]$ is perfect and $ω(H[B])<ω(H)$. We use $P_t$ and $C_t$ to denote a path and a cycle on $t$ vertices, respectively. For two disjoint graphs $F_1$ and $F_2$, we use $F_1\cup F_2$ to denote the graph with vertex set $V(F_1)\cup V(F_2)$ and edge set $E(F_1)\cup E(F_2)$, and use $F_1+F_2$ to denote the 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 prove that (i) $(P_5, C_5, K_{2, 3})$-free graphs are perfectly divisible, (ii) $χ(G)\le 2ω^2(G)-ω(G)-3$ if $G$ is $(P_5, K_{2,3})$-free with $ω(G)\ge 2$, (iii) $χ(G)\le {3\over 2}(ω^2(G)-ω(G))$ if $G$ is $(P_5, K_1+2K_2)$-free, and (iv) $χ(G)\le 3ω(G)+11$ if $G$ is $(P_5, K_1+(K_1\cup K_3))$-free.

No reviews yet.

No comments yet.