不含三角形的某些禁用子图的色数（英文）  

Chromatic Number of Triangle-free Graphs With Some Forbidden Subgraphs

作　　者：王晓[1] 

机构地区：[1]商洛学院数学与计算科学系,商洛陕西726000

出　　处：《数学进展》2015年第5期747-751,共5页Advances in Mathematics（China）

基　　金：Supported by the Natural Science Special Research Foundation of the Education Department of Shaanxi Province(No.12JK089);the Science Research Foundation of Shangluo University(No.12SKY011)

摘　　要：Gyarfas曾猜想:对于一个给定的森林F,存在一个整数函数f(F,ω(G)),满足对任何一个不含F的图G有x(G)≤f(F,ω(G)),其中x(G)和ω(G)分别表示图G的色数和团数.令扫帚图B(m,n)表示将路P_m中的一个度为1的顶点和星K_(1,n)的中心点重合在一块所得到的阶为m+n的树.本文证明了:如果G是一个不含三角形且不含B(m,n)作为导出子图的图,则有x(G)≤m+n-1;对于一个给定的树T,证明了如果G是一个不含三角形且不含C_4和T作为导出子图的图,则有x(G)≤|T|-1.Gyarfas conjectured that for a given forest F, there exists an integer function f（F,ω（G）） such that X（G） ≤ f（F,ω（G）） for any F-free graph G, where χ（G） and w（G） are the chromatic number and the clique number of G, respectively. The broom B（m, n） is the tree of order m ＋ n obtained from identifying a vertex of degree 1 of Pm with the center of K1,n. In this note, we prove that if G is a triangle-free and B（m,n）-free graph, then X（G） ≤ m ＋ n - 1, and for a given tree T, if G is a triangle-free, C4-free and T-free graph, then x（G） ≤ ｜T｜- 1.

关 键 词：色数 不含三角形的图 禁用子图 

分 类 号：O157.5[理学—数学]