东南大学学报（英文版）
東南大學學報（英文版）
동남대학학보（영문판）
JOURNAL OF SOUTHEAST UNIVERSITY
2008年
2期
253-256
,共4页
(k,d)-着色%r-圆着色%圆色数%Mycielski图
(k,d)-著色%r-圓著色%圓色數%Mycielski圖
(k,d)-착색%r-원착색%원색수%Mycielski도
(k,d)-coloring%r-circular-coloring%circularchromatic number%Mycielski's graph
设k和d是2个互素的正整数且k≥2d.Gkd是一个图,它的顶点集合为{0,1,…,k一1},边集合为{ij|d≤|i-j|≤k0d,i,j=0,1,…,k-1}.图G的圆色数Xc(G)定义为使得图G与Gkd同态的2个正整数k和d的最小比值k/d.研究了Xc(G)和Xc(G-v)之间的关系,对任意顶点v求出了Xc(Gkd-v)的精确值,给出了具有对任意顶点Xc(G-v)=Xc(G)-1和其他特定性质的图类;并对图的圆色数的一些下界进行了探讨,给出了图的圆色数达到下界X-1+1/α的充要条件,这里X和α分别是图G的点色数和独立数.
設k和d是2箇互素的正整數且k≥2d.Gkd是一箇圖,它的頂點集閤為{0,1,…,k一1},邊集閤為{ij|d≤|i-j|≤k0d,i,j=0,1,…,k-1}.圖G的圓色數Xc(G)定義為使得圖G與Gkd同態的2箇正整數k和d的最小比值k/d.研究瞭Xc(G)和Xc(G-v)之間的關繫,對任意頂點v求齣瞭Xc(Gkd-v)的精確值,給齣瞭具有對任意頂點Xc(G-v)=Xc(G)-1和其他特定性質的圖類;併對圖的圓色數的一些下界進行瞭探討,給齣瞭圖的圓色數達到下界X-1+1/α的充要條件,這裏X和α分彆是圖G的點色數和獨立數.
설k화d시2개호소적정정수차k≥2d.Gkd시일개도,타적정점집합위{0,1,…,k일1},변집합위{ij|d≤|i-j|≤k0d,i,j=0,1,…,k-1}.도G적원색수Xc(G)정의위사득도G여Gkd동태적2개정정수k화d적최소비치k/d.연구료Xc(G)화Xc(G-v)지간적관계,대임의정점v구출료Xc(Gkd-v)적정학치,급출료구유대임의정점Xc(G-v)=Xc(G)-1화기타특정성질적도류;병대도적원색수적일사하계진행료탐토,급출료도적원색수체도하계X-1+1/α적충요조건,저리X화α분별시도G적점색수화독립수.
For two integers k and d with (k, d) = 1 and k≥2d, letedge if and only if d ≤ | i -j |≤ k - d. The circular chromaticnumber Xc (G) of a graph G is the minimum of k/d for which Gadmits a homomorphism to Gkd. The relationship between Xc(G -v) and Xc (G)is investigated. In particular, the circular chromaticnumber of Gkd - v for any vertex v is determined. Some graphswith Xc ( G - v) =Xc (G) - 1 for any vertex v and with certainproperties are presented. Some lower bounds for the circularchromatic number of a graph are studied, and a necessary andsufficient condition under which the circular chromatic number ofa graph attains the lower bound X - 1 + 1/α is proved, where X isthe chromatic number of G and α is its independence number.
