不含某些导出子图的图的色数

摘要：

根据Gyárfás的猜想，即对于一个给定的森林 F ，存在一个整数函数 f （F ，ω（G）），满足对任何一个不含 F作为导出子图的图G ，有χ（G）≤ f （F ，ω（G）），设 C2，1，n表示将路 P4中的一个度为2的顶点和 Pn的一个端点联结而成的阶为n＋4的树，C2，n ，2表示将路 P5中的中间顶点和 Pn的一个端点联结而成的阶为n＋5的树，得到并证明了每一个不含三角形，不含 C4并且不含 T作为导出子图的图是（n＋2）‐可着色的，这里 T C2，1，n＋1或者 T C2，n，2．

关键词：着色、不含三角形、导出子图

分类号：O157.5(代数、数论、组合理论)

资助基金：Foundation itemSupported by Specific Science Foundation of Shaanxi Province Education Department 12JK0899；Pro-ject of Shangluo University 12SKY011，13JYJX119

在线出版日期：2015-07-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：189-192