论文标题
在某些$ p_5 $ free Graphs的色数上
On the chromatic number of some $P_5$-free graphs
论文作者
论文摘要
令$ g $为图。我们说，如果对于$ g $，$ g $，$ v（h）$的每个感应子图$ h $，可以将$ g $划分为$ a $和$ b $，使$ h [a] $是完美的，而$ω（h [b]）<ω（h）$。我们使用$ p_t $和$ c_t $分别表示$ t $顶点的循环。对于两个不相交的图，$ f_1 $和$ f_2 $，我们使用$ f_1 \ cup f_2 $用顶点套装$ v（f_1）\ cup v（f_2）$和edge set $ e（f_1）\ cup e（f_1）\ cup e（f_1）\ cup e（f_2）$，并使用$ f_1+f_2 $ cup $ cup $ v（f_1） Edge设置$ e（f_1）\ cup e（f_2）\ cup \ {xy \; | \; x \ in V（f_1）\ mbox {and} y \ in V（f_2）\} $。在本文中，我们证明（i）$（p_5，c_5，k_ {2，3}）$ - 免费图是完全可分开的，（ii）$χ（g）\ le2Ω^2（g）-Ω（g）-ch）-x（g）-x（g）-3 $如果$ g $是$ is $ is $ is $（p_5，k_ {2,3}） $χ（g）\ le {3 \ fof 2}（ω^2（g）-Ω（g））$如果$ g $是$（p_5，p_5，k_1+2k_2）$ - 免费，和（iv）$χ（g）\ le3Ω（g）（g）+11 $ g $ g $ g $是$（p_5，k_1+k_1+k_1+cup）。
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.
