王維凡, 楊燦權

(浙江師范大學 數理與信息工程學院,浙江 金華 321004)

0 引 言

本文中所考慮的圖都是有限簡單圖.設V(G),E(G),Δ(G)分別表示圖G的頂點集、邊集和最大度,將Δ(G)簡記為Δ.圖的染色理論是圖論研究的一個重要內容.圖的染色就是對頂點、邊等圖的元素進行分類,使得它們滿足某些特定性質.不同的性質和要求就導出不同的染色方式.圖論染色理論中最經典的染色就是正常點染色和正常邊染色.本文主要研究圖的邊染色.

圖G的一個正常k-邊染色是指一個映射φ:E(G)→{1,2,…,k},使得相鄰的邊染不同的顏色.圖G的邊色數χ′(G)定義為最小的正整數k,使得G有一個正常k-邊染色.

任意一個最大度為Δ的圖G,由于相鄰的邊需要染不同的顏色,自然可以得到χ′(G)≥Δ.1964年,Vizing[1]證明了下面的一個圖論中最重要的結果之一：

定理1[1]對于任意簡單圖G,Δ≤χ′(G)≤Δ+1.

若χ′(G)=Δ,則稱G是第一類的,否則稱G是第二類的.對一般圖而言,盡管只有2個選擇,但要確定是否屬于第一類是NP-完全的[2],于是,學者們開始尋找使圖G是第一類或第二類圖的充分條件.

給定一個最大度為Δ的圖G,設GΔ表示由G的所有最大度點導出的子圖.基于這個特殊的子圖,Fournier[3]給出了下面十分有意義的結果：

定理2[3]對簡單圖G,若GΔ是一個森林,則G是第一類的.

對于平面圖G,Vizing[4]證明了:當Δ≥8時,G是第一類圖;而當2≤Δ≤5時,存在第二類的簡單平面圖G.文獻[4]中提出猜想:當6≤Δ≤7時,簡單平面圖G是第一類的.Sanders等[5]和張利民[6]分別獨立證明了當Δ=7時Vizing猜想成立.但當Δ=6時,該猜想至今懸而未決.很多學者給出了部分結果,如考慮不含特殊長度的圈且最大度為6的平面圖[7-11].更多關于平面圖邊染色的結果可以參考文獻 [12].

為了研究圖的團數與色數之間的關系,Mycielski[13]構造了一類圖,稱之為Mycielski圖,使得它不含三角形但色數可以任意大,從而否定了圖的色數會被其團數界定的一個猜想.文獻[14-15]提出了廣義Mycielski圖的概念,并且研究了它的圓環(huán)色數、圓環(huán)團數、全控制數等若干性質和參數.Tardif[16]也研究了廣義Mycielski圖的分數染色,給出了一個很漂亮的結果.

V(μm(G))=V0∪V1∪…∪Vm∪{w};

圖1 廣義Mycielski圖μm(G)的示意圖

Kwon等[17]證明了：若G是一個不同于K2的連通圖,則μ1(G)是第一類圖.本文將這個結果推廣到廣義Mycielski圖μm(G),其中m≥2.

1 主要結果

Galvin[18]證明了下面結果:

在定理4的證明之前,需要引入一個重要的引理.

引理1[17]對于整數n≥3,若圖G(X∪Y;E)是一個二部圖,且滿足:

1)|X|=|Y|=n+1;

2)N(X)=Y;

則G含有一個完美匹配.

定理4 設G(≠K2)是一個n-階簡單連通圖且m≥2是整數,則χ′(μm(G))=Δ(μm(G)).

|L(e)|≥|C|-1=Δ+1-1=Δ=Δ(G12).

重復以上步驟,并依照奇偶性逐層進行染色,直到μm(G)-w的所有邊被正常染色.此外,對第Vk層的頂點標號要求有特殊性質.其中:若m是偶數,則k=m;若m是奇數,則k=m-1.對1≤i≤Δ+1,設Si表示Vk中標顏色ci∈C的頂點集合,且令si=|Si|.于是,類似于文獻[17]中引理3.3 的證明,可以要求Vk的標號滿足下列附加條件:

(*)對任意2個顏色ci,cj∈C,有|si-sj|≤2.

令s=max{si|i=1,2,…,Δ+1}.由n≤2Δ,n=s1+s2+…+sΔ+1和條件(*),易推出s≤3.

分以下2種情形證明:

1)m是偶數.若對所有i=1,2,…,Δ+1滿足si≥1,則選擇Si中的某個頂點xi,用顏色b(xi)給邊wxi染色.注意到b(xi)∈C,于是與w關聯的Δ+1條邊被正常染色.剩下的n-(Δ+1)≤2Δ-(Δ+1)=Δ-1條邊分別染顏色Δ+2,Δ+3,…,2Δ.進而得到G的一個正常的2Δ-邊染色.否則假設存在某些i∈{1,2,…,Δ+1},使得si=0.由條件(*)推出s≤2.對1≤j≤2,定義

Tj={Si: |Si|=j,1≤i≤Δ+1}.

若|T1|+|T2|=Δ+1,則對每一個Si∈T1∪T2,選擇Si中的某個頂點xi,用顏色b(xi)給邊wxi染色,與w關聯的其余n-Δ-1條邊分別用Δ+2,Δ+3,…,2Δ染色,從而得到G的一個正常的2Δ-邊染色.

下面將通過改染來完成對與w關聯的邊染色.主要分2個步驟:

若Δ=3,則n≤2Δ=6.除了|X1|=3外,其余|Xi|均小于3,而|Z∩X1|≤2,故Δ-|Z∩Xi|≥1,其中1≤i≤4.若Δ≥4,因為|Z∩Xi|≤|Xi|≤si≤3,所以對于所有1≤i≤Δ+1,都有Δ- |Z∩Xi|≥1.因而無論哪種情況,對1≤i≤Δ+1,都有Δ-|Z∩Xi|≥1.故對任意顏色ci∈C,都有

d(ci)≥Δ+1-(|Z∩Xi|+1)≥Δ-|Z∩Xi|≥1.

其中括號里的1表示步驟1中換色可能增加的ci-邊,而增加的ci-邊最多只有一條.這就滿足了引理1的條件2),即N(Z)=C.

2 結 語

本文證明了:若G是一個不同于K2的連通圖,則廣義Mycielski圖μm(G)(m≥2)是第一類的,即χ′(μm(G))=Δ(μm(G))=max{2Δ(G),|V(G)|}.這個結果推廣了文獻[17]中m=1時的結論.特別地,當m=0時,若Δ(G)≤n-2,則μ0(G)是第一類的;若Δ(G)=n-1,且n是一個奇數,則μ0(G)也是屬于第一類的;但是,若Δ(G)=n-1,且n是一個偶數,問題就變得不那么簡單,因為奇階完全圖是屬于第二類的.此外,容易看到,當G是K2時,μm(G)是一個奇圈,因此是第二類的.

[1]Vizing V G.On an estimate of the chromatic class of ap-graph[J].Metody Diskret Anal,1964,3(7):25-30.

[2]Holyer I.The NP-completeness of edge colorings[J].SIAM J Comput,1981,10(4):718-720.

[3]Fournier J C.Méthode et théorème générale de coloration des arêtes[J].J Math Pures Appl,1977,56(4):437-453.

[4]Vizing V G.Critical graphs with a given chromatic class[J].Diskret Analiz,1965,5(1):9-17.

[5]Sanders D P,Zhao Yue.Planar graphs of maximum degree seven are class I[J].J Combin Theory Ser B,2001,83(2):201-212.

[6]Zhang Limin.Every planar graph with maximum degree 7 is of class one[J].Graphs Combin,2000,16(4):467-495.

[7]Zhou Guofei.A note on graphs of class I[J].Discrete Math,2003,262(1/2/3):339-345.

[8]Bu Yuehua,Wang Weifan.Some sufficient conditions for a planar graph of maximum degree six to be class 1[J].Discrete Math,2006,306(13):1440-1445.

[9]Li Xuechao,Luo Rong,Niu Jianbing.A note on class one graphs with maximum degree six[J].Discrete Math,2006,306(13):1450-1455.

[10]Wang Weifan,Chen Yongzhu.A sufficient condition for a planar graph to be class 1[J].Theoret Comput Sci,2007,385(1/2/3):71-77.

[11]Huang Danjun,Wang Weifan.Planar graphs of Maximum degree six without 7-cycles are class one[J].Electr J Comb,2012,19(3):17-21.

[12]Borodin O V.Coloring of plane graphs:A survey[J].Discrete Math,2013,313(4):517-539.

[13]Mycielski J.Sur le coloriage des graphes[J].Colloq Math,1955,3(161/162):9-12.

[14]Lam P B,Lin Wensong,Gu Guohua,et al.Circular chromatic number and a generalization of construction of Mycielski[J].J Combin Theory Ser B,2003,89(2):195-205.

[15]Lin Wensong,Wu Jianzhuan,Lam P B,et al.Several parameters of generalized Mycielskians[J].Discrete Appl Math,2006,154(8):1173-1182.

[16]Tardif C.Fractional chromatic numbers of cones over graphs[J].J Graph Theory,2001,38(2):87-94.

[17]Kwon Y S,Jee J,Zhang Zhongfu.Edge-chromatic numbers of Mycielski graphs[J].Discrete Math,2012,312(6):1222-1225.

[18]Galvin F.The list chromatic index of a bipartite multigraph[J].J Combin Theory Ser B,1995,63(1):153-158.