图的色数与着色数的上界  

Bounds for Chromatic and Coloring Number of Graphs

作　　者：史小艺[1] 张宁[1] 薛婷婷[1] 

机构地区：[1]中国矿业大学理学院,江苏徐州221116

出　　处：《五邑大学学报（自然科学版）》2012年第2期15-17,共3页Journal of Wuyi University(Natural Science Edition)

基　　金：中央高校基本科研业务费专项基金资助(2010LKSX06)

摘　　要：证明了对于围长不少于2k1的图G,其色数X(G)≤c((bk,2k+1+2)n)1/k+1+2,其中c=c(k)且limk→∞ c(k)=1,bt,k是G的booksize.另外还证明了对于围长不少于2k+1的图G,其着色数σ(G)≤[bk,2k+1+1)n/2]1/k+2.In this paper, it is proved that for graph G whose coloring number is X（G）≤c（（bk,2k＋1＋2）n）1/k＋1＋2 where c=c（k）with limk→∞ c（k）=1and whose girth is at least 2k＋1, bl.k is the booksize of G. It is also proved that the coloring number for graph G with girth at least 2k ＋1 is σ（G）≤[bk,2k＋1＋1）n/2]1/k＋2.

关 键 词：无向图 色数 着色数 围长 

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