论文标题
$（p_7，c_4，c_5）$的最佳$χ$ bunds $ - 免费图
The optimal $χ$-bound for $(P_7,C_4,C_5)$-free graphs
论文作者
论文摘要
在本文中，我们给出了$（P_7，C_4，C_5）$ - 免费图形的最佳$χ$结合功能。我们表明，每一个$（P_7，C_4，C_5）$ - 免费图$ G $具有$χ（g）\ le \ lceil \ frac \ frac {11} {9} {9}ω（g）\ rceil $。为了证明结果，我们使用[K。中获得的分解定理。 Cameron and S. Huang and I. Penev and V. Sivaraman, The class of $({P}_7,{C}_4,{C}_5)$-free graphs: Decomposition, algorithms, and $χ$-boundedness, Journal of Graph Theory 93, 503--552, 2020] combined with careful inductive arguments and a nontrivial use of the König定理进行两分匹配。
In this paper, we give an optimal $χ$-binding function for the class of $(P_7,C_4,C_5)$-free graphs. We show that every $(P_7,C_4,C_5)$-free graph $G$ has $χ(G)\le \lceil \frac{11}{9}ω(G) \rceil$. To prove the result, we use a decomposition theorem obtained in [K. Cameron and S. Huang and I. Penev and V. Sivaraman, The class of $({P}_7,{C}_4,{C}_5)$-free graphs: Decomposition, algorithms, and $χ$-boundedness, Journal of Graph Theory 93, 503--552, 2020] combined with careful inductive arguments and a nontrivial use of the König theorem for bipartite matching.
