平面圖的2-面染色的一點(diǎn)注記

王劍宇

(南京曉莊學(xué)院 信息工程學(xué)院，江蘇 南京 210017)

本文所研究的圖均為簡(jiǎn)單無(wú)向圖.如果沒(méi)有特殊說(shuō)明，所有的定義和術(shù)語(yǔ)均可參考[1].以下先給出本文要用的一些定義.

設(shè)圖G=(V,E),其中頂點(diǎn)集是V，邊集是E.對(duì)于G的頂點(diǎn)v，如果d(v)=k，則點(diǎn)v稱(chēng)為k-點(diǎn)；如果d(v)≥k，則點(diǎn)v稱(chēng)為k+-點(diǎn)；如果d(v)≤k，則點(diǎn)v稱(chēng)為k--點(diǎn).如果頂點(diǎn)v滿足d(v)=k，且關(guān)聯(lián)i個(gè)2-點(diǎn)，則稱(chēng)v是ki-點(diǎn).圖G中，最短圈的長(zhǎng)度稱(chēng)為G的圍長(zhǎng)，記為g(G)或g.

若φ是一個(gè)從頂點(diǎn)集V到顏色集{1, 2, …,k}的一個(gè)映射φ：V→{1, 2, …,k}，使得對(duì)于任意u,v∈V,uv∈E，滿足φ(u)≠φ(v)，則稱(chēng)φ是圖G的一個(gè)正常k-染色.使得G存在正常k-染色的最小整數(shù)k，稱(chēng)為G的染色數(shù)，記為χ(G).

一個(gè)圖G稱(chēng)為是平面圖，是指存在的G的一個(gè)平面嵌入，使得每條邊只在頂點(diǎn)相交.平面圖G的頂點(diǎn)集、邊集、面集分別記為V,E,F.給定平面圖G和正整數(shù)l，G的一個(gè)l-面染色是指對(duì)圖的G頂點(diǎn)染色，使得對(duì)于任意兩個(gè)頂點(diǎn)，如果它們?cè)谕粋€(gè)面上，且之間存在不超過(guò)l的通路，所染的顏色不同.G的l-面染色所用的最少的顏色數(shù)稱(chēng)為G的面染色數(shù).顯然，平面圖的1-面染色就是點(diǎn)染色，因此，l-面染色是點(diǎn)染色的自然推廣.

總體而言，平面圖的l-面染色猜想是公開(kāi)的，甚至當(dāng)l=2時(shí)也沒(méi)有解決.

本文主要證明了如下定理：

定理1：如果G是平面圖且圍長(zhǎng)至少是7，那么G的2-面染色數(shù)至多是7.

定理1改進(jìn)Micka?l Montassier和André Raspaud[3]的部分結(jié)論，并且表明如果平面圖G的圍長(zhǎng)至少是7時(shí)，平面圖l-面染色猜想對(duì)于l=2是成立的，對(duì)于該猜想的成立提供了正面的支持.

定理1的證明方法主要采用色擴(kuò)張和權(quán)轉(zhuǎn)移方法，在下文中，第一部分主要討論關(guān)于定理1的極小反例的結(jié)構(gòu)性質(zhì)，第二部分利用權(quán)轉(zhuǎn)移方法證明定理1的極小反例不存在，從而定理1成立.

1 最小反例的結(jié)構(gòu)引理

本節(jié)主要討論極小反例的結(jié)構(gòu).假設(shè)G是一個(gè)定理1的最小的反例，即指，G是一個(gè)g≥7的平面圖，但G不能用7種顏色進(jìn)行2-面染色，而G的任意一個(gè)真子圖G′存在2-面染色只用最多7種顏色.顯然，不妨假設(shè)G是連通的.

以下，我們證明若干引理：

引理1：G中不含1-點(diǎn).

證明：假設(shè)v是G中的一個(gè)1-點(diǎn)，u是唯一一個(gè)和v相鄰的點(diǎn).設(shè)u1、u2與u相鄰(見(jiàn)圖1(a)).因?yàn)镚是最小的反例，所以G-{v}可用最多7種顏色進(jìn)行2-面染色.只要讓v的顏色與u1、u2、u的顏色不同，則G也可用最多7種顏色進(jìn)行2-面染色.

引理2：G中不含相鄰的2-點(diǎn).

證明：假設(shè)v和w是G中的兩個(gè)相鄰的頂點(diǎn)，且d(v)=d(w)=2.設(shè)u1、u2與u相鄰，x1、x2與x相鄰(見(jiàn)圖1(b)).因?yàn)镚是最小的反例，所以G-{v,w}可用最多7種顏色進(jìn)行2-面染色.只要讓v的顏色與u1、u2、u、x的顏色不同，w的顏色與u、v、x、x1、x2的顏色不同，則G也可以用最多7種顏色進(jìn)行2-面染色.

圖1 最小反例中的局部結(jié)構(gòu)

引理3：G中的3-點(diǎn)最多與一個(gè)2-點(diǎn)相鄰.

證明：假設(shè)G中的一個(gè)頂點(diǎn)y與x、z、w相鄰，其中d(y)=3,d(x)=d(z)=2，d(w)≥2.設(shè)u與x相鄰，v與z相鄰，u1、u2與u相鄰，v1、v2與v相鄰，w1、w2與w相鄰(見(jiàn)圖1(c)).因?yàn)镚是最小的反例，所以G-{x,y,z}可用最多7種顏色進(jìn)行2-面染色.只要讓x的顏色與u1、u2、u、w的顏色不同，y的顏色與u、x、w、w1、w2、v的顏色不同，z的顏色與w、x、y、v、v1、v2的顏色不同，則G也可用最多7種顏色進(jìn)行2-面染色.

引理4：G中不含相鄰的31-點(diǎn).

證明：假設(shè)G中有兩個(gè)31-點(diǎn)u和v相鄰.設(shè)s、z與u相鄰，w、t與v相鄰，x1、x2與x相鄰，y1、y2與y相鄰，z1、z2與z相鄰，w1、w2與w相鄰(見(jiàn)圖1(d)).因?yàn)镚是最小反例，所以G-{u,v,s,t}可用最多7種顏色進(jìn)行2-面染色.只要讓u的顏色與x、z、z1、z2、w的顏色不同，v的顏色與z、u、w、w1、w2、y的顏色不同，s的顏色與x1、x2、x、u、z、v的顏色不同，t的顏色與u、v、w、y、y1、y2的顏色不同，則G也可用最多7種顏色進(jìn)行2-面染色.

引理5：G中的4-點(diǎn)最多與兩個(gè)2-點(diǎn)相鄰.

證明：假設(shè)G中的一個(gè)4-點(diǎn)u與x、y、z、w相鄰，其中d(x)=d(y)=d(z)=2，d(w)≥2.設(shè)s與x相鄰，t與y相鄰，v與z相鄰，s1、s2與s相鄰，v1、v2與v相鄰，t1、t2與t相鄰，w1、w2與w相鄰(見(jiàn)圖1(e)).因?yàn)镚是最小的反例，所以G-{u,x,y,z}可用最多7種顏色進(jìn)行2-面染色.只要讓u的顏色與s、v、t、w、w1、w2的顏色不同，x的顏色與s1、s2、s、u、w的顏色不同，y的顏色與x、u、w、t、t1、t2的顏色不同，z的顏色與x、u、w、y、v、v1、v2的顏色不同，則G也可用最多7種顏色進(jìn)行2-面染色.

引理6：G中的3-點(diǎn)最多與兩個(gè)31-點(diǎn)相鄰

證明：假設(shè)G中的一個(gè)3-點(diǎn)u與x、y、z相鄰，其中x、y、z均為31-點(diǎn).設(shè)x0、r與x相鄰，y0、s與y相鄰，z0、t與z相鄰，且d(r)=d(s)=d(t)=2,x1、x2與x0相鄰，y1、y2與y0相鄰，z1、z2與z0相鄰，r0與r相鄰，s0與s相鄰，t0與t相鄰，r1、r2與r0相鄰，s1、s2與s0相鄰，t1、t2與t0相鄰.因?yàn)镚是最小的反例，所以G-{u,x,y,z,r,s,t}可用最多7種顏色進(jìn)行2-面染色(見(jiàn)圖1(f)).只要讓x的顏色與x1、x2、x0、r0的顏色不同，y的顏色與y1、y2、y0、s0、x的顏色不同，z的顏色與z1、z2、z0、t0、x、y的顏色不同，u的顏色與x、x0、y、y0、z、z0的顏色不同，r的顏色與r1、r2、r0、x、x0、u的顏色不同，s的顏色與s1、s2、s0、y、y0、u的顏色不同，t的顏色與t1、t2、t0、z、z0、u的顏色不同，則G也可用最多7種顏色進(jìn)行2-面染色.

2 權(quán)轉(zhuǎn)移及定理的證明

本節(jié)利用權(quán)轉(zhuǎn)移方法并結(jié)合最小反例的結(jié)構(gòu)引理證明最小反例不存在.

引理7：每個(gè)連通的平面圖(V,E,F)滿足：

(1)

(2)

我們給定以下權(quán)轉(zhuǎn)移規(guī)則：

規(guī)則1：每個(gè)3+-點(diǎn)轉(zhuǎn)移權(quán)值1給相鄰的2-點(diǎn).

下面驗(yàn)證G的頂點(diǎn)和面的新權(quán)重.

?f∈F，因?yàn)間≥7，w*(f)=w(f)≥0.

?v∈V，設(shè)v是G中的一個(gè)k-點(diǎn)(k≥2)，則：