不含K_1+P_3和C_4作为导出子图的图的色数

摘要

Erodo¨s证明了对于一个图G,χ(G)-ω(G)可以任意大。因此,对一般图而言,其色数不一定能找到一个与团数有关的上界。文章主要研究了一类F-free图的色数和团数的关系。得到了如果图G是一个不含K1+P3和C4作为导出子图的图,那么当α(G)≥3时,χ(G)=ω(G);当α(G)=2时,χ(G)n≤2ω(G)。