Some results on circular chromatic number of a graph  

图的圆色数的一些结果(英文)

作　　者：吴建专[1] 林文松[1] 

机构地区：[1]东南大学数学系,南京211189

出　　处：《Journal of Southeast University(English Edition)》2008年第2期253-256,共4页东南大学学报（英文版）

基　　金：The National Natural Science Foundation of China(No.10671033)

摘　　要：For two integers k and d with （k, d） = 1 and k≥2d, let G^dk be the graph with vertex set {0,1,…k - 1 } in which ij is an edge if and only if d≤｜ i -j I｜≤k - d. The circular chromatic number χc（G） of a graph G is the minimum of k/d for which G admits a homomorphism to G^dk. The relationship between χc（ G- v） and χc （G）is investigated. In particular, the circular chromatic number of G^dk - v for any vertex v is determined. Some graphs withx χc（G - v） =χc（G） - 1 for any vertex v and with certain properties are presented. Some lower bounds for the circular chromatic number of a graph are studied, and a necessary and sufficient condition under which the circular chromatic number of a graph attains the lower bound χ- 1 ＋ 1/α is proved, where χ is the chromatic number of G and a is its independence number.设k和d是2个互素的正整数且k≥2d.Gdk是一个图,它的顶点集合为{0,1,…,k-1},边集合为{ijd≤i-j≤k-d,i,j=0,1,…,k-1}.图G的圆色数χc(G)定义为使得图G与Gkd同态的2个正整数k和d的最小比值k/d.研究了χc(G)和χc(G-v)之间的关系,对任意顶点v求出了χc(Gkd-v)的精确值,给出了具有对任意顶点χc(G-v)=χc(G)-1和其他特定性质的图类;并对图的圆色数的一些下界进行了探讨,给出了图的圆色数达到下界χ-1+1/α的充要条件,这里χ和α分别是图G的点色数和独立数.

关 键 词：（k  d）-coloring r-circular-coloring circular chromatic number Mycielski＇ s graph 

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