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

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

2、色數(shù)與色數(shù)相等的一個(gè)充分條件。 定理A設(shè)X(G)=n，如果點(diǎn)集V存在一個(gè)非空真子集A，使得對(duì)G的任一個(gè)n-著色c的每一色類X都有X∈A或者X∩A=φ，那么Xc(G)=X(G)。 由這個(gè)定理很容易得到下面的推論A。 推論A設(shè)圖G有n個(gè)點(diǎn)，如果G存在一個(gè)點(diǎn)的度為n-1，那么Xc(G)=X(G)。 本文證明了如果G存在一個(gè)點(diǎn)的度為n-2，那么Xc(G)=X(G).這個(gè)結(jié)論是定理B(范更華[6])的一個(gè)推論。

3、 定理B設(shè)Xc(G)=k/d，其中k，d互素，那么對(duì)于V(G)中的任意一個(gè)元素v都有d(v)≤|V(G)|-2d+1。 然而，若圖G存在一個(gè)度為n-3的點(diǎn)，則不一定有Xc(G)=X(G)。因此本文在對(duì)有一個(gè)點(diǎn)的度為n-3的圖上增加限制條件，使得Xc(G)=X(G)。定理1所描述的圖就是其中一類。 定理1設(shè)圖G有n個(gè)點(diǎn)，如果G有3個(gè)互不相鄰的點(diǎn)，并且其中一個(gè)點(diǎn)的度為n-3，那么Xc(G)=X(G)。 除此之外，

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

5、究了Mycielski圖的圓色數(shù)與色數(shù)相等的問(wèn)題，得到下面一個(gè)定理。 定理C設(shè)圖G有n個(gè)點(diǎn)，若G含有一個(gè)五個(gè)點(diǎn)的完全子圖，并且這五個(gè)點(diǎn)的度都為n-3，存在另外一個(gè)點(diǎn)與這五個(gè)點(diǎn)都不相鄰，那么Xc(M(G))=X(M(G))。 本文把五個(gè)點(diǎn)改進(jìn)到四個(gè)點(diǎn)，得到下面這個(gè)定理：定理4設(shè)圖G有n個(gè)點(diǎn)，若G有四個(gè)點(diǎn)的度為n-3，并且存在另外兩個(gè)點(diǎn)與這四個(gè)點(diǎn)都不相鄰，那么Xc(M(G))=X(M(G))。 對(duì)于含有度為n-2的圖

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

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

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