圖乘積的分數色數

孔靜

(泰山學院數學與系統科學學院，山東泰安 271021)

這樣我們就可以將染色問題轉化成下面的整數規劃問題(Ⅰ):

1 引言

自從18世紀Euler開始對圖論進行研究，圖論吸引了越來越多學者的目光，并且已經成為了一個十分重要的研究領域.圖的染色問題是圖論中一個非常重要的問題，在實際生活中有著廣泛的應用.染色問題中一個非常著名的問題就是四色定理，在其被探討的百年期間大大推動了圖論的發展.

一個圖G的k正常著色，是指將G的頂點分配k中顏色，使得染同一種顏色的任意兩個頂點在圖G中沒有邊相連，即等價于染同一種顏色的頂點構成了圖G的一個獨立點集.一個圖G的正常著色所需的最小的k的值稱為圖G的色數，記為χ(G)=k.在人們對圖的染色問題用各種方法進行研究的同時，也引申出了與圖的染色問題密切相關的一些新的領域，如圖的分數染色.對圖的分數染色的研究最早可追溯到對圖的多重染色的研究.E.Scheinerma，D.Ullman在文［1］對分數染色的問題進行了系統的闡述.在該書中，作者首先給出了對圖的理論進行分數推廣的方法，特別對于染色問題，引出了分數染色的概念，它是對圖的染色問題的一個推廣.

我們可以將染色問題轉化為一個線性規劃問題.因為染同一種顏色的點在圖G中構成了圖G的獨立點集，而圖的一個染色就將G的頂點集分割成由獨立點集構成的集合.因此我們可以將求一個圖的色數問題轉化成尋找G的若干獨立集，使得這些獨立集的個數最少，并且滿足:G的任意頂點x都至少包含在一個獨立集中.我們將所有頂點和所有獨立集分別進行標號，V(G)={v1，v2，…，vn}，I(G)={I1，I2，…，Im}可以得到一個0－1矩陣M=(mij)n×m(稱為頂點—獨立集關系的描述矩陣)，其中

這樣我們就可以將染色問題轉化成下面的整數規劃問題(Ⅰ):

這里My≥1中的1是全1的m維列向量.

我們將上面規劃的約束放寬，由要求y∈{0，1}，變為要求y≥0，這樣得到一個線性規化問題(Ⅱ):

已知任意一個圖的染色問題，即整數規劃問題(Ⅰ)是一個NP－complete問題.而上面的線性規劃問題(Ⅱ)有多項式時間的算法.設整數規劃問題(Ⅰ)的最優解為y*，線性規化問題(Ⅱ)的最優解為y＊＊，顯然y＊＊≤y*.這樣我們可以用y＊＊對y*進行估計.因為線性規劃問題(Ⅱ)的解是一個有理數，所以對任意給定一個圖G，我們定義為分數色數，記為χf(G).

目前人們對分數染色的研究一般集中在兩個方面，一是研究一些特殊圖的分數色數，如Kneser圖，循環圖等及一些圖的運算下的分數色數［1－4］.如對圖的乘積，已經證明了對于任意的兩個圖G1和G2，G1和G2的分隔乘積(記為G1*G2)，G1和G2的字典序乘積(記為G1［G2］)都滿足:χf(G1*G2)= χf(G1)χf(G2)≤χ(G1)χ(G2)，χf(G1［G2］)=χf(G1)χf(G2)［1］.另一方面研究一些有關圖的染色的猜想是否關于圖的分數著色依然成立，如Ed¨os－Faber－Lovásze猜想，Hadwiger猜想等等［1］.因此，此領域還有大量的未解決的問題有待研究.

在本文中我們對兩個圖的強乘積的分數色數進行了研究.任意給定兩個圖G和H，我們證明了ω(G)ω(H)≤χf(GH)≤χ(G)χ(H)，這樣就可以通過圖G和H本身的性質來對它們的強乘積的分數色數進行估計.

2 基本概念

對于無向圖G=(V，E)，我們分別用V(G)和E(G)表示圖G的頂點集合和邊集合.設頂點{u，v}?V(G)，我們用無序頂點對uv來標記圖中的一條邊，記u，v是這條邊的頂點，并且稱u，v與該邊相關聯，反之亦然.與同一條邊相關聯的兩個頂點稱為是相鄰的，與同一個頂點相關聯的兩條邊也稱為是相鄰的.頂點重合為一點的邊稱為環.如果一個圖的頂點集和邊集都是有限集，我們稱之為有限圖.在本文中我們考慮的都是沒有重邊和環的有限的無向圖.

每一對頂點都有一條邊相連的圖稱為完全圖.V(G)中一個子集稱為一個團，如果該子集中任意兩個點在G中都相鄰.而如果S?V(G)中任意兩點在G中都不相鄰，則稱S為G的一個獨立集.設C是G的任意一個獨立集，如果C不包含在G的其他獨立集中，那么我們稱C是一個極大獨立集.我們用IG表示G的所有極大獨立集的集合;用I(G)表示G的所有獨立集集合.G中包含頂點最多的團稱為最大團，其所包含頂點的個數稱為G的團數，我們用ω(G)表示.G的所有團的集合我們用C(G)表示.

設頂點集V1?V(G)，V2?V(G)，則V1×V2={(v1，v2)∶v1∈V1，v2∈V2}.下面我們定義兩個圖G和H的幾種乘積形式.G和H的強乘積，用GH表示，它是這樣一個圖，其頂點集是{(u，v)∶u∈V(G)，v∈V(H)}=V(G)×V(H);兩個頂點(u，x)(v，y)如果滿足下面三個條件中其中一條:

(1)uv∈E(G)，xy∈E(H);

(2)uv∈E(G)，x=y;

(3)u=v，xy∈E(H).

兩個圖G和H的分隔乘積，記為G*H，頂點集是V(G)×V(H);兩個頂點(u，x)(v，y)∈E(G*H)當且僅當uv∈E(G)或者xy∈E(H).

其他的有關圖論的定義和符號請參見文獻［5］.

3 主要結果

我們將對強乘積圖的分數色數進行討論，證明下面的定理.

定理1任意給定兩個圖G和H，ω(G)ω(H)≤χf(GH)≤χ(G)χ(H).

我們首先證明兩個引理.

引理1 設I，J分別為圖G和H的極大獨立集，則I×J一定為GH的一個極大獨立集.

引理2 設C，Q分別為圖G和H的最大團，則C×Q一定為GH的一個最大團，即ω(GH)= ω(G)ω(H).

證明:因為C，Q分別為圖G和H的團，因此根據強乘積的定義，C×Q中的每一個頂點在GH中都是相鄰的，因此C×Q一定為GH的一個團.C×Q的頂點個數為|C|×|Q|，由C，Q分別為圖G和H的最大團知，C×Q的頂點個數在GH的所有團中也是最大的.因此C×Q一定為GH的一個最大團.

分隔乘積也是圖乘積的一種.對于兩個圖G和H的分隔乘積G*H，我們已知下面的結論成立.

引理3［1］任意給定兩個圖G和H，則I，J分別為圖G和H的極大獨立集等價于I×J為G*H的一個極大獨立集.

引理4［1］對于圖G和H，χf(G*H)=χf(G)χf(H)≤χ(G)χ(H).

下面我們給出定理1的證明.

證明:對于圖G和H，我們求χf(GH)就是求解線性規劃(Ⅱ'):

設求χf(G*H)對應的線性規劃(Ⅳ)為:

其中B是G*H的頂點——極大獨立集關系的0－1描述矩陣.由引理1和引理3知，{I×J∶I∈IG，J∈IH}=IG*H?IGH，從而矩陣B是由A的若干列向量構成的子矩陣，這意味著線性規劃(Ⅳ)的一個可行解一定為線性規劃(Ⅲ)的可行解，因此χf(G?H)≤χf(G*H).又根據引理4，

故

另一方面，線性規劃(Ⅲ)的對偶規劃為(DⅢ):其對應的整數規劃為(IDⅢ)

由矩陣A的定義知，(IDⅢ)是從G?H的頂點集中挑選部分頂點，使這些頂點不在同一個獨立集中，也就是說在同一個團中.因此(IDⅢ)的最優值是圖G?H的最大團所含頂點的個數，即最大團數ω(G?H)，因此(DⅢ)的最優值是分數最大團數，我們用ωf(G?H)表示，顯然ωf(G?H)≥ω(G?H).又由線性規劃的對偶性質知，ωf(G?H)=χf(G?H).由引理2可得

綜合(1)和(2)即得:

［1］E.Scheinerma，D.Ullman.Fractional graph theory，a rational approach to graph theory［M］.New York:J.Wiley and Sons，1997.

［2］孫磊.Kneser圖的分數染色的臨界性［J］.物理學學報，2002，22(A)2:238－243.

［3］G.J.Chang，L.Huang，X.Zhu.The circular chromatic numbers and the fractional chromatic number of distance graphs［J］.European Journal of Combinatorics，1998，19:423－431.

［4］D.C.Fish.Fractional colorings with large denominators［J］.Journal of Graph Theory，1995，20:403－409.

［5］J.A.Bondy，U.S.R.Murty.Graph theory with applications［M］.New York:Elsevier Science Publishing Co.，Inc，1976.