For a graph $G$, $\chi(G)$ $(\omega(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 $\chi(G)\leq \frac{3}{2}\omega(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 $\chi(H)\geq\frac{10}{7}\omega(H)$. This generalizes/improves several previously known results in the literature.
翻译:对于一个G$G$, $\chi( G) $( g) $( g) $) 表示它的色( clotic) 号。 A $P_ 5美元是五个脊椎上的无弦路径, $4 美元旋转美元是由四个脊椎上的无弦循环构成的图表, $C_ 4美元, 加上与所有脊椎相邻的额外的顶点。 在本文中, 我们显示每张( P_ 5 美元, $4 轮) 表示它的无色( g) $( g)\ g)\leq\ frac\ {%2 ⁇ omega( G) $( g) 。 此外, 这个约束几乎是紧凑的。 也就是说, 每张( P_ 5 美元, 4 美元 滚动) 无弦的图形都有 $\ call L$( ) $H\ cal $\ g$\ leglefleman ( h)\ g)\ geqq\\\\\\\\\ 7\ omegamega( h) $( H) $.