兩類n-部圖及其補圖的無圈染色

彭 悅，田雙亮

(西北民族大學 數(shù)學與計算機科學學院，甘肅 蘭州 730030)

0 引言

本文所考慮的圖G都是有限無向的簡單連通圖，用V(G)與E(G)分別表示G的頂點集和邊集，用Δ(G)表示G的最大度，并記(x)k=xmodk，其中x為整數(shù)，k為正整數(shù)，用rH表示r個同構于圖H的圖的不交并，其中r≥2.

無圈染色概念是Grünbaum于1973年在文獻[1]中用代入法求解稀疏對稱Hessian矩陣的高速計算背景下產(chǎn)生的.Fertin等人在文獻[2]中給出了d-維網(wǎng)格的無圈色數(shù)的上界為d+1；無圈染色是NP問題，其在特殊圖類上的復雜性的大多數(shù)結果都是否定的.特別地，即使僅限于二部圖[3-4]，這個問題仍是NP問題.文獻[5]證明了三連通圖的無圈色數(shù)為4，除非它是K4或者K3，3，否則K4和K3，3的無圈色數(shù)是5.根據(jù)無圈染色定義，顯然有以下兩個引理：

引理1若G的連通分支為G1,G2,…，Gω，則a(G)=max{a(Gi)|1≤i≤ω}.

本文主要研究完全n-部圖Kr1,r2,…，rn與二部圖rC2n及其補圖的無圈染色.文中未說明的符號和術語見文獻[6].

1 主要結果及其證明

關于完全n-部圖及其補圖的無圈染色有以下結果：

定理1對于任意正整數(shù)r1,r2,…，rn，有

先證明a(G)≥m-r+1.假設a(G)≤m-r，且σ是G的一個(m-r)-無圈染色.為敘述方便，用C(S)表示頂點子集S中頂點在σ下的顏色構成的集合，下文含義相同，不再贅述.顯然，有

1≤|C(Vi)|≤ri,i=1,2,…,n；

C(Vi)∩C(Vj)=φ,i,j=1,2,…，n,i≠j;

易證，存在惟一i0∈{1,2,…，n}，使得|C(Vi0)|

這與σ的定義矛盾.假設存在i0,i1∈{1,2,…，n}，使得i0≠i1，且 |C(Vi0)|

由定理1可直接得到以下推論：

關于二部圖rC2n及其補圖的無圈染色，有以下結果：

顯然，G是具有二分類(X,Y)的二部圖.

|C(Y)|=rn.又因σ所用顏色數(shù)為2rn-3，所以C(X)∩C(Y)=.另外，可以證明以下結論：

1) 存在i0∈{1,2,…，r}，使得C(Xi0)∩C(Yi0)≠.

2) 若存在i0∈{1,2,…，r}，使得C(Xi0)∩C(Yi0)≠，則對任意j∈{1,2,…，r}-{i0}，有C(Xj)∩C(Yj)=.

3)C(X)∩C(Y)≤2.

事實上，假設結論1)不成立，即對任意j∈{1,2,…，r}，使得C(Xj)∩C(Yj)=.取a∈C(X)∩C(Y)，則存在不同整數(shù)i0,j0∈{1,2,…，r}，使得a∈C(Xi0)，a∈C(Yi0)，于是存在x∈Xi0，y∈Yi0，使得σ(x)=σ(y)=a.注意到，Xio中頂點與Yio中頂點在中都是相鄰的，所以x與y在中相鄰，這就產(chǎn)生相鄰頂點染相同顏色的情況，與σ的定義矛盾.因此，結論1)成立.

假設結論2)不成立，即存在j0∈{1,2,…，r}-{i0}，使得C(Xj0)∩C(Yj0)≠.取a∈C(Xi0)∩C(Yi0)，b∈C(Xj0)∩C(Yj0)以及x∈Xi0，y∈Yi0，x＇∈Xj0，y＇∈Yj0使得σ(x)=σ(y)=a，σ(x＇)=σ(y＇)=b,顯然a≠b.在中，因Xi0中頂點與Yj0中頂點都是相鄰的，Xj0中頂點與Yi0中頂點都是相鄰的，所以x與y＇相鄰，y與x＇相鄰.而x與x＇，y與y＇在中相鄰，于是形成了4階2色圈：C4=xy＇yx＇x，這與σ定義矛盾.因此，結論2)成立.