關(guān)于圖的圓色數(shù)和圓團數(shù).pdf

1、圓色數(shù)Xc(G)作為色數(shù)概念的一個推廣首先是由朱緒鼎在提出的，并且他在這篇文章中證明了任一個圖的圓色數(shù)與它的星色數(shù)相等。星色數(shù)X*(G)是由A.Vince在[18]中建立的，同時A.Vince給出了星色數(shù)與色數(shù)大小的一個關(guān)系式，即X(G)-1＜X*(G)≤X(G)。因此，對所有的圖G都有X(G)-1＜Xc(G)≤X(G)。 朱緒鼎證明了某些圖的Xc(G)可以任意地接近X(G)-1。另外，某些圖的圓色數(shù)與色數(shù)相等，定理A就是關(guān)于圓

2、色數(shù)與色數(shù)相等的一個充分條件。 定理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).這個結(jié)論是定理B(范更華[6])的一個推論。

3、 定理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)。 除此之外，

4、本文討論了有兩個點的度為n-3的圖，這種圖可以分為五類，其中兩類圖可以得到Xc(G)=X(G)結(jié)論。定理2和定理3就是這兩種情況。 定理2設圖G有n個點，如果G有兩個不相鄰的點的度都為n-3，并且存在第三點與這兩個點都不相鄰，那么Xc(G)=X(G)。 定理3設圖G有n個點，如果G有兩個相鄰的點的度都為n-3，并且存在另外兩個點與這兩點都不相鄰，那么Xc(G)=X(G)。 顯然，定理2是定理1的一個推廣。范更華研

5、究了Mycielski圖的圓色數(shù)與色數(shù)相等的問題，得到下面一個定理。 定理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的圖

6、，它們的Mycielski圖的圓色數(shù)與色數(shù)也可以相等，見定理5。 定理5設圖G有n個點，若G有一個階為3的團，并且這個團里的所有點的度為n-2，那么Xc(M(G))=X(M(G))。 在其它條件不變的情況下，定理5中的階數(shù)3是不可改進的。 關(guān)于Kneser圖的圓色數(shù)和色數(shù)問題，有下面兩個主要定理： 定理D對任一大于或等于4的整數(shù)m，都有Xc(KG(m，2))=X(KG(m，2))。定理E對于任一大于或等于

7、4，但不等于5的整數(shù)m，都有Xc(KG2(m，2))=X(KG2(m，2))。 本文證明了定理D和定理E中某些Kneser圖在Mycielski結(jié)構(gòu)下，它們的圓色數(shù)依然等于色數(shù)。 定理6對于任一大于或等于16的整數(shù)m，都有Xc(M(KG(m，2)))=X(M(KG(m，2)))。 定理7.對于任一大于或等于20的整數(shù)m，都有Xc(M(KG2(m，2)))=X(M(KG2(m，2)))。 問題1在定理6和定

8、理7中，整數(shù)m的下界是否可以改進? 問題2如果Xc(G)=X(G)，那么，什么因素決定Xc(M(G))=X(M(G))? 關(guān)于圓團數(shù)問題，就任意兩個圖的cartesian積證明了以下結(jié)論： 定理F如果ωc(G)≠2+2/d，那么ωc(G×H)=max{ωc(G)，ωc(H)}。 該文在第三章中主要研究了Mycielski圖M(G)的圓團數(shù)和圖G的圓團數(shù)之間的關(guān)系，以及兩個圖的categorical積的圓團