摘要
Gyárfás曾猜想,设F是一个森林,对于每一个F-free的图G,存在整数函数f(F,ω(G))使得χ(G)f(F,ω(G))。利用一个引理,得到了每一个不含{M(p,q),C3,C4}作为导出子图的图是(p+q-1)-可着色的。
Abstract Gyátfás conjectured that for a forest F, every F-free graph exists an integer function f（F,ω（G）） such that χ（G）≤f（F,ω（G））. By a lemma, the result that every {M（p,q）,C3 ,C4 }-free graph is （p＋q-1）-colourable was obtained.
出处
《计算机与数字工程》
2015年第7期1325-1327,共3页
Computer & Digital Engineering
基金
陕西省科技厅基金(编号:2014JM2-1007)
商洛学院科研基金(编号:12SKY011)资助
关键词
色数
导出子图
限制子图
chromatic number, induced subgraph, forbidden subgraph
