纺织高校基础科学学报Issue(2)：189-192,4.DOI:10.13338/j.issn.1006-8341.2015.02.010
不含某些导出子图的图的色数
The chromatic number of graphs without certain induced subgraphs
摘要
Abstract
According to Gyárfás conjectured that for a given forest F ,there exists an integer function f (F ,ω(G)) such that χ(G)≤ f (F ,ω(G)) for any F‐free graph G .Let C2 ,1 ,n be the tree with order n+4 obtained from P4 and Pn by joining a vertex v (with dP4 (v)=2) of P4 and one endvertex of Pn ,C2 ,n ,2 be the tree with order n+5 obtained from P5 and Pn by joining the mid‐dle vertex of P5 and one endvertex of Pn .It is proved that every triangle‐free ,C4‐free and T‐free graph is (n+2)‐colourable where T C2 ,1 ,n+ 1 or T C2 ,n,2 .关键词
着色/不含三角形/导出子图Key words
colouring/triangle-free/induced subgraph分类
数理科学引用本文复制引用
王晓..不含某些导出子图的图的色数[J].纺织高校基础科学学报,2015,(2):189-192,4.基金项目
Foundation itemSupported by Specific Science Foundation of Shaanxi Province Education Department （12JK0899）；Pro-ject of Shangluo University （）
