solidot新版网站常见问题，请点击这里查看。
消息
本文已被查看6956次
Coloring graphs with no induced five-vertex path or gem. (arXiv:1810.06186v1 [math.CO])
来源于:arXiv
For a graph $G$, let $\chi(G)$ and $\omega(G)$ respectively denote the
chromatic number and clique number of $G$. We give an explicit structural
description of ($P_5$,gem)-free graphs, and show that every such graph $G$
satisfies $\chi(G)\le \lceil\frac{5\omega(G)}{4}\rceil$. Moreover, this bound
is best possible. 查看全文>>
