论文部分内容阅读
圆色数Xc(G)作为色数概念的一个推广首先是由朱绪鼎在提出的，并且他在这篇文章中证明了任一个图的圆色数与它的星色数相等。星色数X*(G)是由A.Vince在[18]中建立的，同时A.Vince给出了星色数与色数大小的一个关系式，即X(G)-1＜X*(G)≤X(G)。因此，对所有的图G都有X(G)-1＜Xc(G)≤X(G)。
朱绪鼎证明了某些图的Xc(G)可以任意地接近X(G)-1。另外，某些图的圆色数与色数相等，定理A就是关于圆色数与色数相等的一个充分条件。
定理A设X(G)=n，如果点集V存在一个非空真子集A，使得对G的任一个n-着色c的每一色类X都有X∈A或者X∩A=φ，那么Xc(G)=X(G)。
由这个定理很容易得到下面的推论A。
推论A设图G有n个点，如果G存在一个点的度为n-1，那么Xc(G)=X(G)。
本文证明了如果G存在一个点的度为n-2，那么Xc(G)=X(G).这个结论是定理B(范更华[6])的一个推论。
定理B设Xc(G)=k/d，其中k，d互素，那么对于V(G)中的任意一个元素v都有d(v)≤|V(G)|-2d+1。
然而，若图G存在一个度为n-3的点，则不一定有Xc(G)=X(G)。因此本文在对有一个点的度为n-3的图上增加限制条件，使得Xc(G)=X(G)。定理1所描述的图就是其中一类。
定理1设图G有n个点，如果G有3个互不相邻的点，并且其中一个点的度为n-3，那么Xc(G)=X(G)。
除此之外，本文讨论了有两个点的度为n-3的图，这种图可以分为五类，其中两类图可以得到Xc(G)=X(G)结论。定理2和定理3就是这两种情况。
定理2设图G有n个点，如果G有两个不相邻的点的度都为n-3，并且存在第三点与这两个点都不相邻，那么Xc(G)=X(G)。
定理3设图G有n个点，如果G有两个相邻的点的度都为n-3，并且存在另外两个点与这两点都不相邻，那么Xc(G)=X(G)。
显然，定理2是定理1的一个推广。范更华研究了Mycielski图的圆色数与色数相等的问题，得到下面一个定理。
定理C设图G有n个点，若G含有一个五个点的完全子图，并且这五个点的度都为n-3，存在另外一个点与这五个点都不相邻，那么Xc(M(G))=X(M(G))。
本文把五个点改进到四个点，得到下面这个定理：定理4设图G有n个点，若G有四个点的度为n-3，并且存在另外两个点与这四个点都不相邻，那么Xc(M(G))=X(M(G))。
对于含有度为n-2的图，它们的Mycielski图的圆色数与色数也可以相等，见定理5。
定理5设图G有n个点，若G有一个阶为3的团，并且这个团里的所有点的度为n-2，那么Xc(M(G))=X(M(G))。
在其它条件不变的情况下，定理5中的阶数3是不可改进的。
关于Kneser图的圆色数和色数问题，有下面两个主要定理：
定理D对任一大于或等于4的整数m，都有Xc(KG(m，2))=X(KG(m，2))。定理E对于任一大于或等于4，但不等于5的整数m，都有Xc(KG2(m，2))=X(KG2(m，2))。
本文证明了定理D和定理E中某些Kneser图在Mycielski结构下，它们的圆色数依然等于色数。
定理6对于任一大于或等于16的整数m，都有Xc(M(KG(m，2)))=X(M(KG(m，2)))。
定理7.对于任一大于或等于20的整数m，都有Xc(M(KG2(m，2)))=X(M(KG2(m，2)))。
问题1在定理6和定理7中，整数m的下界是否可以改进?
问题2如果Xc(G)=X(G)，那么，什么因素决定Xc(M(G))=X(M(G))?
关于圆团数问题，就任意两个图的cartesian积证明了以下结论：
定理F如果ωc(G)≠2+2/d，那么ωc(G×H)=max{ωc(G)，ωc(H)}。
该文在第三章中主要研究了Mycielski图M(G)的圆团数和图G的圆团数之间的关系，以及两个图的categorical积的圆团数与原图之间的关系。定理8对任意图G，有ωc(M(G))=ωc(G)。
定理9对任意图G和H，有ωc(G()H)=min{ωc(G)，ωc(H)}。