李 梅, 田大東

(中國礦業(yè)大學(xué) 理學(xué)院,江蘇 徐州 221116)

邊染色 9-臨界圖邊數(shù)的新下界

李 梅, 田大東

(中國礦業(yè)大學(xué) 理學(xué)院,江蘇 徐州 221116)

臨界圖;邊數(shù);下界;度

Key words:critical graphs;size of edge;lower size;degrees

0 引 言

文中討論的圖都是有限、無向的簡單圖。有限圖是指圖的點(diǎn)集、邊集都是有限集;無向圖是指圖的邊均為無向邊;簡單圖是指無環(huán)且無多重邊的圖。有關(guān)的定義或符號可參考文獻(xiàn)[2]。

1 預(yù)備知識

定義 1設(shè) G是一個(gè)圖,用 d(v)、V(G)、E(G)、Δ(G)、δ(G)、δ1(x)、m及 q分別表示 G的頂點(diǎn)的度數(shù)、頂點(diǎn)集、邊集、最大度、最小度、x相鄰頂點(diǎn)的最小度數(shù)、邊數(shù)及平均度。

定義 2若對圖 G的任何邊 e,令 G′=G-e,如果χ′(G′)<χ′(G),則稱 G是臨界的。若 G是臨界的且Δ(G)=Δ,則稱 G是Δ-臨界圖。其中,χ′(G)表示圖 G邊色數(shù)。

引理 1[3](Vizing鄰接引理) 設(shè) G是Δ-臨界圖,xy∈E(G),d(x)=k,則 y至少有Δ-d(x)+1個(gè)Δ度鄰點(diǎn)。

引理 2[4]設(shè) G是Δ-臨界圖,xy∈E(G),且d(x)+d(y)=Δ +2,則有 :

(1)x、y的所有鄰點(diǎn) (除去 x、y)均為Δ度點(diǎn);

(2)與 x、y距離為 2的頂點(diǎn)的度至少為Δ-1;

(3)當(dāng) d(x)、d(y)<Δ時(shí),與 x、y距離為 2的頂點(diǎn)的度為Δ。

引理 3[4]設(shè) G是Δ-臨界圖,Δ≥5,d(x)=3,則 x至少有兩個(gè)Δ度鄰點(diǎn),它的頂點(diǎn)中除了 x外其余的點(diǎn)的度都大于等于Δ-1。

引理 4[5]設(shè) G是Δ-臨界圖,d(x)=4,若Δ≥6,則有:

(1)若 x鄰接一個(gè)Δ-2度頂點(diǎn),則 x的其他鄰點(diǎn)均為Δ度頂點(diǎn);

(2)若 x的鄰點(diǎn)全是大于等于Δ-1度頂點(diǎn),并且其中一個(gè)鄰接 3個(gè)小于等于Δ-2度頂點(diǎn),則 x的其他 3個(gè)鄰點(diǎn)只鄰接一個(gè)小于等于Δ-2度頂點(diǎn),即x;

(3)若 x鄰接兩個(gè)Δ-1度頂點(diǎn),則 x的兩個(gè)Δ度鄰點(diǎn)只鄰接一個(gè)小于等于Δ-2度頂點(diǎn),即 x。

引理 5[6]設(shè) G是Δ-臨界圖,d(x)=4,x有一個(gè)Δ-1度鄰點(diǎn),設(shè)為 w。如果 w(除 x外)還鄰接一個(gè)Δ-1度頂點(diǎn),則 x的其他三個(gè)鄰點(diǎn)均為Δ度頂點(diǎn),并且每一個(gè)Δ度頂點(diǎn)的鄰點(diǎn)度均大于等于Δ-1。

引理 6[4]設(shè) G是Δ-臨界圖,d(x)=5,如果有一個(gè)Δ-2度鄰點(diǎn) w,則有:

(1)如果w除了 x外還鄰接一個(gè)小于等于Δ-2度頂點(diǎn),則 x的其余的四個(gè)鄰點(diǎn)均為Δ度頂點(diǎn),并且除了 w外,所有鄰點(diǎn)的度均大于等于Δ-1;

(2)如果 w僅有一個(gè)小于等于Δ-2度鄰點(diǎn),即x,則 x有三個(gè)大于等于Δ-1度鄰點(diǎn) (至少包括兩個(gè)Δ度點(diǎn))滿足:Δ度頂點(diǎn)最多與兩個(gè)小于等于Δ-2度頂點(diǎn)相鄰,Δ-1度點(diǎn)僅與一個(gè)小于等于Δ-2度頂點(diǎn)相鄰,即 x。

引理 7[5]設(shè) G是Δ-臨界圖,xy∈E(G),z∈N(x)y,d(x)<Δ,則有:

τ(y,x,z)≥2Δ -d(x)-d(y)+1。

其中,τ(y,x,z)表示 z的鄰點(diǎn)中 (不包含 x)度數(shù)大于等于 3Δ-d(x)-d(y)-d(z)+2的頂點(diǎn)數(shù)。

引理 8[6]設(shè) G是Δ-臨界圖,d(x)=6,δ1(x)表示 x的最小度鄰點(diǎn)的度數(shù),如果δ1(x)=Δ-2或δ1(x)=Δ-1,則有兩種情形。

情形 1δ1(x)=Δ-2,

(1)如果這個(gè)最小度鄰點(diǎn)與三個(gè)小于等于Δ-2度頂點(diǎn)相鄰,那么 x的其他 5個(gè)鄰點(diǎn)全部都是Δ度頂點(diǎn),且這些Δ度鄰點(diǎn)僅與一個(gè)小于等于Δ-2度頂點(diǎn)相鄰,即 x;

(2)如果這個(gè)最小度鄰點(diǎn)與兩個(gè)小于等于Δ-2度頂點(diǎn)相鄰,則 x有四個(gè)大于等于Δ-1度鄰點(diǎn) (至少包括兩個(gè)Δ度頂點(diǎn))滿足:Δ度頂點(diǎn)最多與兩個(gè)小于等于Δ-2度頂點(diǎn)相鄰,Δ-1度頂點(diǎn)僅與一個(gè)小于等于Δ-2度頂點(diǎn)相鄰,即 x;

(3)如果這個(gè)最小度鄰點(diǎn)與一個(gè)小于等于Δ-2度頂點(diǎn)相鄰,即 x,則 x的所有Δ度頂點(diǎn)最多與三個(gè)小于等于Δ-2度頂點(diǎn)相鄰。

情形 2δ1(x)=Δ-1,

(1)如果這個(gè)最小度鄰點(diǎn)與四個(gè)小于等于Δ-3度頂點(diǎn)相鄰,那么 x的其他 5個(gè)鄰點(diǎn)全部都是Δ度頂點(diǎn),且這些Δ度鄰點(diǎn)僅與一個(gè)小于等于Δ-2度頂點(diǎn)相鄰,即 x;

(2)否則,x的所有Δ-1度鄰點(diǎn)最多只能與三個(gè)小于等于Δ-3度頂點(diǎn)相鄰。

2 主要結(jié)果

證明 運(yùn)用 Discharging方法,按照差值轉(zhuǎn)移規(guī)則 (差值規(guī)則大部分是根據(jù)臨界圖的鄰接性質(zhì)得到的)對相鄰的頂點(diǎn)之間進(jìn)行差值轉(zhuǎn)移,使得最終的所有頂點(diǎn)的值都能滿足要求。

(1)對 d(x)=2的點(diǎn),

設(shè) x是一個(gè) 2度點(diǎn),x鄰接兩個(gè)Δ度頂點(diǎn),設(shè)為u、v,由引理 2,u至少鄰接 7個(gè)不同于 v的Δ度頂點(diǎn),v同樣如此,則根據(jù)規(guī)則 1,有

(2)對 3≤d(x)≤7的點(diǎn),

如果 d(x)+δ1(x)=Δ+2,設(shè) y為 x的度數(shù)為δ1(x)的一個(gè)鄰點(diǎn),根據(jù)引理 2,x鄰接 d(x)-1個(gè)Δ度頂點(diǎn),考慮到 x、y可能同時(shí)鄰接某些個(gè)Δ度頂點(diǎn),所以這些Δ度鄰點(diǎn)至少向 x轉(zhuǎn)移差值:

經(jīng)過差值轉(zhuǎn)移所得新值為

下文對各點(diǎn)只從 d(x)+δ1(x)≥Δ+3情況開始考慮。

(3)對 d(x)=3的點(diǎn),

(4)對 d(x)=4的點(diǎn),

如果δ1(x)=8,分兩種情形來進(jìn)行討論:

情形 1x有一個(gè) 8度鄰點(diǎn),設(shè)為 w,再分兩種情況。

(i)w除 x外還鄰接一個(gè)小于等于 8度點(diǎn),則由引理 5知,x的其他三個(gè)鄰點(diǎn)均為Δ度點(diǎn),且它們的鄰點(diǎn)度數(shù)均大于等于 8,則所以由規(guī)則 2,得

(ii)w除 x外不與任何小于等于 8度點(diǎn)相鄰,則由引理 4,如果 x(除 w外)的三個(gè)Δ度鄰點(diǎn)中有一個(gè)與三個(gè)小于等于Δ-2度點(diǎn)相鄰,則其余兩個(gè)Δ度點(diǎn)的鄰點(diǎn)的度數(shù)均大于等于 8,由規(guī)則 2知

否則,x的所有鄰點(diǎn)最多鄰接兩個(gè)小于等于Δ-2度頂點(diǎn),此時(shí)

如果δ1(x)=9,根據(jù)引理 4分兩種情形來進(jìn)行討論:

情形 2如果w僅有一個(gè)小于等于Δ-2度鄰點(diǎn),即 x,則 x有三個(gè)大于等于Δ-1度鄰點(diǎn) (至少包括兩個(gè)Δ度點(diǎn))滿足:Δ度頂點(diǎn)最多與兩個(gè)小于等于Δ-2度頂點(diǎn)相鄰,Δ-1度點(diǎn)僅與一個(gè)小于等于Δ-2度頂點(diǎn)相鄰,即 x。所以

(5)對 d(x)=5的點(diǎn),

如果δ1(x)=7,設(shè) x的這個(gè) 7度鄰點(diǎn)為 w,則根據(jù)引理 6分兩種情形來討論。

情形 1 w除了 x外還鄰接一個(gè)小于等于Δ-2度頂點(diǎn),則 x的其余的四個(gè)鄰點(diǎn)均為Δ度頂點(diǎn),并且這些Δ度鄰點(diǎn)除了 x外,所鄰接的點(diǎn)的度均大于等于Δ-1,所以

如果δ1(x)=8,分三種情形來討論:

(6)對 d(x)=6的點(diǎn),

如果δ1(x)=7,設(shè) x的這個(gè) 7度鄰點(diǎn)為 w,則根據(jù)引理 8分三種情形來討論:

情形 1w鄰接三個(gè)小于等于Δ-2度頂點(diǎn),則x其余的鄰點(diǎn)均為Δ度頂點(diǎn),且這些Δ度點(diǎn)除了 x外,所鄰接的點(diǎn)的度均大于等于Δ-1,則由規(guī)則 2,

情形 2如果w鄰接兩個(gè)小于等于Δ-2度點(diǎn),則 x有四個(gè)大于等于Δ-1度鄰點(diǎn) (至少包括兩個(gè)Δ度點(diǎn))滿足:Δ度頂點(diǎn)最多與兩個(gè)小于等于Δ-2度頂點(diǎn)相鄰,Δ-1度點(diǎn)僅與一個(gè)小于等于Δ-2度頂點(diǎn)相鄰,即 x。所以

情形 3w僅鄰接一個(gè)小于等于Δ-2度頂點(diǎn),即 x,則 x的每一個(gè)Δ度鄰點(diǎn)至多鄰接三個(gè)小于等于Δ-2度頂點(diǎn),所以

如果δ1(x)=8,分四種情形來討論。

情形 2x有兩個(gè) 8度鄰點(diǎn),則

情形 3x有三個(gè) 8度鄰點(diǎn),則

情形 4x有四個(gè) 8度鄰點(diǎn),則

(7)對 d(x)=7的點(diǎn),則由引理 3,x至少鄰接兩個(gè) 9度頂點(diǎn),所以

(8)對 d(x)=8的點(diǎn),根據(jù)規(guī)則 4,可得

c′(x)≥0。

(9)對 d(x)=9的點(diǎn),如果δ1(x)=2,則由規(guī)則1,可得

c′(x)≥0。

證畢。

3 結(jié)束語

[1] YAP H P.On critical graphs with respect to edge colorings[J].DiscreteMath,1981,37(1):289-296.

[2] 邦 迪.圖論及其應(yīng)用[M].北京:科學(xué)出版社,1984.

[3] V IZI NG V G.Critical graphs with a given chromatic class[J].DiskretAnaliz,1965(5):9-17.

[4] ZHAO YUE.New lower bounds for the size of edge chromatic critical graphs[J].J.Graph Theory,2004,46(2):81-92.

[5] WOODALL D R.The average degree of an edge-chromatic critical graph[J].J.Graph Theory,2007,56(3):194-218.

[6] L I SHUCHAO,L IXUECHAO.Edge coloringof graphswith small maximum degrees[J].Discrete Mathematics,2009,309(14):4 843-4 852.

[7] 曲積彬.最大度為 9和 10時(shí)邊染色臨界圖的下界[J].黑龍江科技學(xué)院學(xué)報(bào),2007,17(6):479-482.

(編輯 王 冬)

New lower bound for size of edge chromatic critical graphs with max imum degree 9

L IM ei, TIAN Dadong
(College of Sciences,China University ofMining&Technology,Xuzhou 221116,China)

O157.5

A

1671-0118(2010)05-0406-05

2010-05-17

李 梅 (1984-),女,山東省臨沂人,碩士,研究方向:計(jì)算數(shù)學(xué),E-mail:wenwen5566ly@sina.com。