大围长图的广义无圈染色  

The Generalized Acyclic Chromatic Number of Graphs with Large Girth

作　　者：蔡建生[1] 王光辉[2] 闫桂英[3] 

机构地区：[1]潍坊学院数学与信息科学学院,潍坊261061 [2]山东大学数学学院,济南250100 [3]中国科学院数学与系统科学研究院,北京100190

出　　处：《数学学报（中文版）》2013年第1期27-30,共4页Acta Mathematica Sinica：Chinese Series

基　　金：国家自然科学基金(11001055);山东省自然科学基金(ZR2009AM009;ZR2011AL008)资助项目

摘　　要：图的顶点染色称为是r-无圈的,如果它是正常染色,使得每一个圈C上顶点的颜色数至少为min{|C|,r}.图G的r-无圈染色数是图G的r-无圈染色中所用的最少的颜色数.我们证明了对于任意的r≥4,最大度为△、围长至少为2(r-1)△的图G的r-无圈染色数至多为6(r-1)△.A vertex coloring of a graph G is called r-acyclic if it is a proper vertex coloring such that every cycle C receives at least min{｜C｜,r} colors.The r-acyclic chromatic number of G is the least number of colors in an r-acyclic coloring of G.We prove that for any number r≥4,the r-acyclic chromatic number of any graph G with maximum degree△and with girth at least 2（r—1）△is at most 6（r—-1）△.

关 键 词：围长 染色 无圈染色 局部引理 

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