论文摘要
图G的星色数x*（G）（亦称圈色数）,是G的色数x（G）的一个自然推广,它最早由Vince在文献[1]中提出.对两个整数k和d,若1≤k≤d,图G的（k,d）-着色定义为映射c:V（G）→{0,1,2,…,k-1},使得当xy∈E（G）时,有d≤|c（x）-c（y）|≤k-d成立。一个图G的星色数x*（G）=inf{k/d:G存在一个（k,d）-着色且2d≤k≤|V（G）|}。此后,朱绪鼎在文献[3]中给出了它的一个等价定义-圈色数。为统一起见,本文统一称为圈色数。 本文研究了平面图、Mycielski图和距离图这三类特殊图的圈色数。本文一共分为五个部分,第一部分为引言,介绍了圈色数的定义及其等价定义,还总结了后面常会引用的定理和结论。第二、三、四部分分别总结了关于平面图、Mycielski图和距离图的圈色数的一些结论和这些问题的进展情况。其中第二部分在总结平面图的圈色数已有结论的基础上,还构造了一些新的圈色数为3或4的平面图。第五部分为展望,总结了关于这三类特殊图的圈色数的一些还未解决的问题。