Coloring_of_some_crown-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 (H)$ and $E(G\cup H)=E(G)\cup E(H)$. The {\em join} $G+H$ is the graph with $V(G+H)=V(G)+V(H)$ and $E(G+H)=E(G)\cup E(H)\cup \{xy|x\in V(G),y\in V(H)$$\}$. We use $P_k$ to denote a {\em path} on $k$ vertices, use {\em fork} to denote the graph obtained from $K_{1,3}$ by subdividing an edge once, and use {\em crown} to denote the graph $K_1+K_{1,3}$. In this paper, we show that (\romannumeral 1) $\chi (G)\le \frac{3}{2}({\omega }^2(G)-\omega (G))$ if $G$ is (crown, $P_5$)-free, (\romannumeral 2) $\chi (G)\le \frac{1}{2}({\omega }^2(G)+\omega (G))$ if $G$ is (crown, fork)-free, and (\romannumeral 3) $\chi (G)\le \frac{1}{2}{\omega }^2(G)+\frac{3}{2}\omega (G)+1$ if $G$ is (crown, $P_3\cup P_2$)-free.

arXiv admin note: text overlap with arXiv:2302.06800