【作者】 张丽丽；

【导师】 许宝刚；

【作者基本信息】 南京师范大学 ， 运筹学与控制论， 2005， 硕士

【摘要】 一个图G的圆色数x_c（G）是图G的色数x（G）的自然推广,最初是由Vince于1988年以“星色数”的定义提出来的。朱绪鼎在文献[3]中用类似Hajos定理的一些操作,利用G_k^d的复制,构造了所有圆色数至少是k/d的图,k/d≥3。本文利用此文献中的三种操作构造了圆色数相等的一类图,计算出结果图S₁,S₂,S₃[3]的圆团数,在此基础上给出S₁,S₂,S₃[3]为圆不完美的充分条件,同时给出如下定理[3]的简化证明:如果r≥3,G₁,G₂,…G₇是圆色数至少为r的图,则x_c（S₃）≥r。文章的最后给出了圆色数的另一等价定义:任意图G,x_c（G）=min{k/d|2d≤k≤|V（D）|且ξ_k,d（G）≤k/d}。（其中D是G的定向图）更多还原

【Abstract】 The circular chromatic number of a graph is a natural generalization of the chromatic number of a graph introduced by Vince in 1988 under the name " the star chromatic number " . Zhu presented 3 operations [3] that do not decrease the circular chromatic number, these operations will be used to replace the Hajos’ sum to construst all graphs of circular chromatic number at least k/d from copies of G_k^d , k/d ≥ 3. In this thesis , we construct a class of graphs which have the same circular chromatic number by zhu’s 3 operations and calculate the circular clique number of the resulting graphs S₁, S₂, S₃[3]. Based on these results , we give some sufficient conditions for S₁, S₂, S₃[3] to be circular imperfect .At the same time , we present a simple proof of the following theorem [3] : if r ≥3 and G₁, G₂, ...... G₇ are graphs with circular chromatic number at least r ,then Xc（S₃） ≥ r . At last ,we give another equivalent definition for circular chromatic number : For any graph G, Xc（G） = min{k/d\2d ≤ k ≤| V（D） | and ξ_k,d（G） ≤ k/d}.（ D is an orientation of G ）更多还原