最大度是6的圖的2-距離列表染色

王玥，孫磊

(山東師范大學數學與統計學院，山東濟南　250014)

?

最大度是6的圖的2-距離列表染色

王玥，孫磊

(山東師范大學數學與統計學院，山東濟南250014)

2-距離染色；列表染色；最大平均度；權轉移①

0　引言

1977年Wegner在[2]中首次提出2-距離染色并證明了Δ=3的平面圖是8-2-距離可染的. 并提出以下猜想：

1　結構性質

斷言1δ(G)≥2.

證明：令v∈V(G)，v為1-點. 根據G的極小性，則G-{v}有一個2-距離列表染色. 由于v至多禁止6種顏色，因此可以給G一種10-2-距離列表染色，與G是最小反例矛盾.

斷言22-點的2個鄰點x,y有d(x)+d(y)≥10.

證明：令v為2-點. 2-點的2個鄰點x,y有d(x)+d(y)≤9. 根據G的極小性，則G-{v}+xy有一個2-距離列表染色. 對v進行染色，則v至多禁止9種顏色(由公式(1)給出)

(1)

因此可以給G一種10-2-距離列表染色，與G是最小反例矛盾.

斷言33-點不能與2-點相鄰.

證明：先來證明3-點不能同時與3個2-點相鄰. 令v為3-點，其鄰域為v1,v2,v3，并且有d(v1)=d(v2)=d(v3)=2，NG(v1){v}={x},NG(v2){v}={y},NG(v3){v}={z}. 由G的極小性可知，G-vv1有一個2-距離列表染色，并在G-vv1中抹去v1,v的顏色. 依次對v1,v進行染色,則v1至多禁止8種顏色 ，(由公式(2)給出)

(2)

而v至多禁止6種顏色，(由公式(3)給出)

(3)

因此可以給G一種10-2-距離列表染色，與G是最小反例矛盾.

再來證明3-點不能同時與2個2-點相鄰. 令v為3-點，其鄰域為v1,v2,z，并且有d(v1)=d(v2)=2，NG(v1){v}={x},NG(v2){v}={y}.由G的極小性可知，G-vv1有一個2-距離列表染色 ，并在G-vv1中抹去v1,v的顏色. 依次對v,v1進行染色，則v至多禁止9種顏色，(由公式(4)給出)

(4)

而v1至多禁止9種顏色，(由公式(5)給出)

(5)

因此可以給G一種10-2-距離列表染色，與G是最小反例矛盾.

最后來證明3-點不能與1個2-點相鄰. 在這種情況下仍進行反證，不失一般性假設3-點v與1個2-點v1相鄰，并且其另外兩個鄰點x，y有d(x)+d(y)≤8，NG(v1){v}={z}. 根據G的極小性，G-{v1}+vx有一個2-距離列表染色. 依次對v1進行染色，此處注意到在這種情況下v1至多禁止9種顏色，(由公式(6)給出)

(6)

因此可以給G一種10-2-距離列表染色，與G是最小反例矛盾.

斷言44-點的結構：

(4.1)4-點不能同時與4個2-點相鄰.

(4.2)若4-點v與3個2-點相鄰，即v1,v2,v3，有d(v1)=d(v2)=d(v3)=2，則v的另外一個鄰點為4+-點.

證明：

先來證明斷言(4.1)， 令v為4-點，其鄰域為v1,v2,v3,v4，并且有d(v1)=d(v2)=d(v3)=d(v4)=2，NG(v1){v}={x},NG(v2){v}={y},NG(v3){v}={z},NG(v4){v}={w}. 由G的極小性可知，G-vv1有一個2-距離列表染色，并在G-vv1中抹去v1,v的顏色. 依次對v1,v進行染色，則在這種情況下v1至多禁止9種顏色，(由公式(7)給出)

(7)

而v至多禁止8種顏色，(由公式(8)給出)

(8)

因此可以給G一種10-2-距離列表染色，與G是最小反例矛盾 .

再來證明斷言(4.2)，令v為4-點，其鄰域為v1,v2,v3,w，并且有d(v1)=d(v2)=d(v3)=2，NG(v1){v}={x},NG(v2){v}={y},NG(v3){v}={z}.不失一般性假設，w為3--點. 由G的極小性可知，G-vv1有一個2-距離列表染色，并在G-vv1中抹去v1,v的顏色. 依次對v1,v進行染色，則在這種情況下v1至多禁止9種顏色，(由公式(9)給出)

(9)

而v至多禁止9種顏色，(由公式(10)給出)

(10)

因此可以給G一種10-2-距離列表染色，與G是最小反例矛盾.

2　定理1的證明

(1)6-點：由R1知，6-點轉移后的權值為，

(2)5-點：由R2知，5-點轉移后的權值為，

(3)4-點：由R3知，分以下幾種情況進行討論：

情形1 v至多鄰接2個2-點：4-點轉移后的權值為，

情形2 v鄰接3個2-點：4-點轉移后的權值為，

(4)3-點：根據斷言3，3-點沒有向其他點轉移權值，因此μ*(v)≥3.

(5)2-點：根據斷言2以及轉移規則，分以下情況進行討論:

情形1 v是(4,6)-點：2-點轉移后的權值為，

情形2 v是(5,5)-點：2-點轉移后的權值為，

情形3 v是(5,6)-點：2-點轉移后的權值為，

情形4 v是(6,6)-點：2-點轉移后的權值為，

綜上所述，對G中的每一個點v都有,

綜上所述，該結果進一步拓展了Δ(G)=6的圖類的2-距離可選性.

[1]Wegner G.Graphs with given diameter and a coloring problem[R].Dortmund:Technical Report,1977.

[2]Bondy J A, Murty U S R. Graph theory with applications [M]. North-Holland: Elsevier, 1981.

[3]Lih K W,Wang Weifan, Zhu Xuding.Coloring the square of aK4-minor free graph [J]. Discrete Math, 2003, 269(1/2/3):303-309.

[4]Borodin O V, Ivanova A O.2-distance (Δ+2)-coloring of planar graphs with girth six and Δ≥18[J].Discrete Math ,2009,309(23):6496-6502.

[5]Oleg V. Borodin,Anna O. Ivanova.List 2-distance (Δ+2)-coloring of planar graphs with girth six[J].European Journal . 2009, 50(1):958.

[6]卜月華,朱旭波. 不含短圈的平面圖的2-距離染色[J]. 中國科學:數學,2012,42(6):635-644.

[7]Cranston D W, Erman R, Skrekovski R.Choosability of the square of a planar graph with maximum degree four[J].Australas J Combin,2014,59(1):86-97.

[8]Daniel W. Cranston, Riste krekovski. Sufficient sparseness conditions for G2to be ( Δ + 1 ) -choosable, when Δ ≥ 5[J]. Discrete Applied Mathematics,2014,162(6):167.

[9]Haiyang Zhu,Lifeng Hou,Wei Chen,Xinzhong Lü.The L ( p , q ) -labelling of planar graphs without 4-cycles[J]. Discrete Applied Mathematics ,2014,162(10):355-363.

[10]Dvorak Z,Kral D,Nejedly,et al.Coloring squares of planar graph with girth six[J].European Cpmbin,2008,29(3): 838-849.

[11]Boccaletti, Stefano, The structure and dynamics of multilayer networks[J].Physics Reports, 2014,544: 1-122.

[12]M. Cygan, J.F. Hou, L. Kowalik, B. Luzar, J.L. Wu, A planar linear arboricity conjecture[J].J. Graph Theory ,2012,69: 403-425.

[13]J. Akiyama, G. Exoo, F. Harary, Covering and packing in graphs III: cyclic and acyclic invariants[J].Math. Slovaca,1980,30: 405-417.

[14]L. Kowali, J.S. Sereni, R. Skrekovski, Total coloring of plane graphs with maximum degree nine[J].SIAM J. Discrete Math,2008,22: 1462-1479.

[15]G. Chartrand, H.V. Kronk, C.E. Wall, The point-arboricity of a graph[J]. Israel J. Math,1968,6: 169-175.

[16]E.G. Coffman, M.R. Garey, D.S. Johnson, et al, Scheduling file transfers[J]. SIAM J. Comput,1985,14: 744-780.

[責任編輯：房永磊]

The List 2-Distance Coloring of a Graph with Maximum Degree Six

WANG Yue，SUN Lei

(School of Mathematics and Statistics, Shandong Normal University, Ji’nan 250014, China)

2-distance coloring ; list coloring ; maximum average degree ; discharge method

2016-09-01

國家自然科學基金(項目編號：11271365)； 山東省自然科學基金(項目編號：ZR2014JL001)；山東師范大學數學科學學院研究生創新基金.

王玥(1991-)，女，山東濟南人，山東師范大學數學與統計學院2014級在讀碩士研究生，主要從事圖論與組合優化的研究.孫磊(1971-)，女，山東濟南人，山東師范大學數學與統計學院副教授，博士，主要從事圖論與組合優化的研究.

O157.5

A

1004-7077(2016)05-0019-05