论文标题
着色（$ p_5 $，$ 4 $ - 轮） - 免费图形
Coloring of ($P_5$, $4$-wheel)-free graphs
论文作者
论文摘要
对于图$ g $，$χ（g）$ $（ω（g））$表示其色度（集团）编号。 $ p_5 $是五个顶点上的和弦路径，$ 4 $ - $ wheel $是由四个顶点上的无弦循环组成的图表$ c_4 $，再加上与$ c_4 $的所有顶点相邻的另一个顶点。在本文中，我们表明每个（$ p_5 $，$ 4 $ -wheel） - 免费图$ g $满足$χ（g）\ leq \ frac {3} {2} {2}ω（g）$。而且，这种界限几乎很紧。也就是说，有一类（$ p_5 $，$ 4 $ -wheel） - free Graphs $ \ cal l $，使每个图$ h \ in \ cal l $ in \ cal l $满足$χ（h）\ geq \ frac \ frac {10} {7} {7} {7}ω（h）$。这将概括/改善文献中的几个先前已知的结果。
For a graph $G$, $χ(G)$ $(ω(G))$ denote its chromatic (clique) number. A $P_5$ is the chordless path on five vertices, and a $4$-$wheel$ is the graph consisting of a chordless cycle on four vertices $C_4$ plus an additional vertex adjacent to all the vertices of the $C_4$. In this paper, we show that every ($P_5$, $4$-wheel)-free graph $G$ satisfies $χ(G)\leq \frac{3}{2}ω(G)$. Moreover, this bound is almost tight. That is, there is a class of ($P_5$, $4$-wheel)-free graphs $\cal L$ such that every graph $H\in \cal L$ satisfies $χ(H)\geq\frac{10}{7}ω(H)$. This generalizes/improves several previously known results in the literature.
