关于临界的圆色数的一个注记  

A Note on the Circular Chromatic Number of Chromatic Critical Graphs

作　　者：杨海燕[1] 许宝刚[1] 

机构地区：[1]南京师范大学数学与计算机科学学院,江苏南京210097

出　　处：《南京师大学报（自然科学版）》2005年第4期38-40,共3页Journal of Nanjing Normal University(Natural Science Edition)

基　　金：国家自然科学基金资助项目(10371055)

摘　　要：圆色数是正常着色的一个推广,由V ince在1988年首次提出.现我们考虑这样一个问题:对于ε>0,是否存在一个具有高连通性的临界图G使得χc(G)≤χ(G)-1+ε?对此,Steffen和Zhu已证明对m≥4存在满足要求的m-连通(m+1)-临界图,只留下一种情形未解决,即G的连通度为3时的情形.在这篇文章中我们就此情形进行讨论,并给出肯定结论.Circular coloring, first introduced by Vince, is a natural generalization of classical coloring. We consider the question： Let ε 〉 0 be a positive number, do there exist a critical graphs G of high connectivity such that Xc（G）≤X（G）-1＋ε？ Steffen and Zhu proved that for any integer m≥4, there is a m-connected （m ＋ 1）-critical graph satisfying the reqest, where some marginal situations are left. In this paper, we give a positive answer to the situation.

关 键 词：圆色数 临界图 连通度 

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