圍長至少為21的平面圖的鄰和可區(qū)分的頂點列表色數(shù)

包一萍

（浙江師范大學(xué)數(shù)理與信息工程學(xué)院，浙江金華321004）

圍長至少為21的平面圖的鄰和可區(qū)分的頂點列表色數(shù)

包一萍

（浙江師范大學(xué)數(shù)理與信息工程學(xué)院，浙江金華321004）

設(shè)f是從圖G的頂點集合V到整數(shù)集合N的一個映射，令每一個點v的鄰和為Sf（v）=Σu∈NG（v）f（u），若f滿足任意相鄰兩點的鄰和不相等，則稱f是圖G的一個鄰和可區(qū)分的頂點列表標號。設(shè)L為圖G的一個k-列表配置，對任意點v有f（v）∈L（v）。若存在最小的正整數(shù)k使得對任意L，圖G都有一個鄰和可區(qū)分的頂點列表標號f，則稱k為圖G的鄰和可區(qū)分的頂點列表色數(shù)，ηl（G）。證明當(dāng)平面圖G的圍長至少為21時，圖G的鄰和可區(qū)分的頂點列表色數(shù)ηl（G）至多為3。

頂點列表色數(shù)；權(quán)轉(zhuǎn)移方法；組合零點定理

0 引言

對于圖的鄰和可區(qū)分的頂點列表標號，已經(jīng)有許多的結(jié)論被證明[1-5]。在2009年，Czcrwinski，Grytczuk和Zelazny[1]提出了一個重要猜想：對于任意圖G，有η（G）≤χ（G）。這個猜想仍未被證明。如果這個猜想是正確的，那么顯然對于任意平面圖G會有η（G）≤4。好多學(xué)者在平面圖中研究鄰和可區(qū)分的頂點列表標號，并且得到了一系列結(jié)果。現(xiàn)在已知的最好的上界是468[2]。針對3-可染平面圖，文獻［2］中有結(jié)論：若G是一個3-可染平面圖，則有η（G）≤36。針對限定了圍長最小值的平面圖，文獻［2］認為：任意一個圍長至少為13的平面圖G，有η（G）≤4。

本文主要研究的是限定了圍長最小值的平面圖的鄰和可區(qū)分的頂點列表色數(shù)。這個問題最開始在2015年被Brandt，Diemunsch和Jahanbekam[4]研究，他們提出了以下結(jié)論：

定理 令G為圍長是g的平面圖。

（1）若g≥5，則ηl（G）≤19；

（2）若g≥6，則ηl（G）≤9；

（3）若g≥7，則ηl（G）≤8；

（4）若g≥26，則ηl（G）≤3。本文主要提出了如下結(jié)論：

定理1令G為圍長是g的平面圖。若g≥21，則ηl（G）≤3。

證明上述定理的方法主要為極小反例和權(quán)轉(zhuǎn)移方法[6-8]。首先，我們主要介紹了一些利用組合零點定理[9]可以簡化的構(gòu)形。接著，我們證明了在極小反例中這些構(gòu)形是不可避免的，最后利用權(quán)轉(zhuǎn)移證明極小反例不存在，從而完成我們對定理1的證明。

1 可被k-簡化的構(gòu)形

圖G被稱作k-嚴格的。如果ηl（G）＞k且對任意非空頂點子集X，有ηl（G-X）≤k。若H是圖G的一個導(dǎo)出子圖，則把H和G中與H中的點相關(guān)聯(lián)的邊一起叫做圖G的一個構(gòu)形。稱一個構(gòu)形是可被k-簡化的，如果在任意k-嚴格的圖G中都不存在該構(gòu)形。本章節(jié)主要介紹一些可被k-簡化的構(gòu)形。

對于V（G）的子集X，令NG（X）=∪v∈XNG（v），用E X][ 表示由X導(dǎo)出的子圖G X][ 中的邊集。令

對于Z∈E*（X），用X[ Z ]表示與Z中某條邊的某個端點相關(guān)聯(lián)的X中的點構(gòu)成的集合。

引理1 在圖G中，令X為V（G）的一個子集，對于任意一條邊e=wv∈E*（X），令若在P'X的展開式中存在一個度為 E*（X） 的滿足 η（u）≤k-1的系數(shù)非零的單項式則 G 不是 k-嚴格的。

證明 假設(shè)G是k-嚴格的，L是G的一個k-列表分配，顯然有L不是G的一個鄰和可區(qū)分的頂點列表標號。因為G是k-嚴格的，所以G-X有一個鄰和可區(qū)分的L-頂點列表標號f。對于任意的u∈X，令xu是一個表示u的標號的變量。對于E*（X）中的任意一條邊e=wv，令其中ce是一個常數(shù)。令在G上的延拓是G的一個鄰和可區(qū)分的L-頂點列表標號當(dāng)且僅當(dāng)PX（cu：u∈X）≠0。這里 PX（cu：u∈X）是在多項式 PX中令 xu=cu之后得到的式子。根據(jù)組合零點定理，若存在 cu∈L（u）使得 PX（cu：u∈X）≠0，則會有一個度為 E*（X） 的滿足 η（u）≤k-1的單項式，其在PX的展開式中的系數(shù)非零。因為我們感興趣的是在PX的展開式中度為 E*（X）的單項式的系數(shù)，所以在Qe中的常數(shù)ce可以被忽略。也就是說，度為 E*（X）的單項式在展開式P'X中的系數(shù)與其在展開式PX中的系數(shù)相同。因此根據(jù)我們的假設(shè)可以推出G有一個鄰和可區(qū)分的L-頂點列表標號，矛盾。

引理2 假設(shè)V（G）的一個子集X導(dǎo)出一個二分子圖（U，W），如圖1。如果二分子圖滿足下列條件

2）對于任意邊 xy∈E[ NG（ U）] ，有 NG（x）∩U=NG（y）∩U；對于任意邊 xy∈E[ NG（ U）] ，有 NG（x）∩W=NG（y）∩W。

3）對于任意集合 Z∈E*（X），有Z ≤（k-1）X[Z]，則G不是k-嚴格的。

圖1 可被k-簡化的構(gòu)形

證明 假設(shè)L是G的一個k-列表分配。如果G是k-嚴格的，則G-X有一個鄰和可區(qū)分的L-頂點列表標號f。下面我們需要證明f可以被延拓成G上的一個鄰和可區(qū)分的L-頂點列表標號。令f'為f在X上的延拓。對于滿足條件2的任意邊xy∈E[ NG（ U）]來說，有Sf（'x）-S（fx）=Sf（'x）-S（fy）。因為邊xy對于f來說是好的，所以對于f'來說邊xy也是好的。同理，對于滿足條件2的任意邊xy∈E[ NG（ W）]來說，xy對于f'均是好的。所以為了證明f'是存在的，我們只需要保證E*（X）中的邊關(guān)于f'來說都是好的。

首先，在由邊集E*（X）導(dǎo)出的子圖中，給E*（X）的邊一個定向，使得NG（U）中的點均為起點，NG（W）中的點均為終點。 若對于任意一條邊e=vw∈E*（X），當(dāng)邊e的方向由v指向w時，我們令中每一個xu出現(xiàn)的正負性均相同（也就是說，xu均以-xu的形式在Qe中出現(xiàn)，或者均以+xu的形式出現(xiàn)在Qe中）。

又因為對于E*（X）中的任意子集Z，有Z ≤（k-1）X [ Z]，根據(jù)霍爾定理 [10 ]可以發(fā)現(xiàn)滿足條件的映射π是存在的。

根據(jù)引理2，我們可以得到下述推論，推論1在 [ 4 ]中也有提到。

對于整數(shù)i＞1以及點v，令dG，（iv）=｛u∈NG（v）：dG（u）=i｝。如果邊e=uv是一條割邊，在G-e的連通分支中包含u的那一支是一棵樹T，則稱割邊e是v的一條懸掛邊，稱連通分支T是v的一個懸掛分支。令σ（v）表示 v的懸掛邊的數(shù)目，且令 β（v）=dG（v）- σ（v）。

推論 2 假設(shè) G 是 3- 嚴格的，路 P=v1v2v3v4v5，滿足 β（vi）=2（i=1，2，3，4，5），則 G 中不包含這樣的路P。

證明 如果G中出現(xiàn)上述的路，運用引理2，其中k=3以及X=｛v2，v3，v4｝∪X（'X'是v1，v2，v3，v4和v5的懸掛分支的集合）。

推論3 假設(shè)G是3-嚴格的且C是G中一個長度至少為21的圈。如果C至少有16個β（v）=2的點v，且恰好有4個β（u）=3的點u，則C至少有兩個β（w）≥4的點w。

證明 假設(shè)C中至多有一個β（w）≥4的點w。如果C中不存在β（w）≥4的點w，則運用引理2，其中k=3，X為C中β（v）=2的點v以及β（v）≤3的點v的懸掛分支的集合。否則，令w為C中β（w）≥4的唯一一個點，同樣運用引理2，其中k=3，X為β（v）=2的與w不相鄰的點v以及β（v）≤3的點v的懸掛分支的集合。

2 定理1的證明

定理1令G為圍長是g的平面圖。若g≥21，則ηl（G）≤3。

證明 假設(shè)上述定理不正確并令圖G是點最少的極小反例。因此圖G是連通的且非樹（由于樹的鄰和可區(qū)分的頂點列表色數(shù)是2）。一條割邊e叫做是必要的，如果G-e的每一個連通分支都包含一個圈。對于圖G的任意一個點v，令E（v）E'（v）和E（v）分別表示與v相關(guān)聯(lián)的邊的集合，與v相關(guān)聯(lián)的必要的割邊的集合以及與v相鄰的面的集合。令

給每一個點v個初始權(quán)d（v）-4并且給每一個面f一個初始權(quán)（lf）-4，同時運用下述權(quán)轉(zhuǎn)移規(guī)則。

R1 每一個1度點從它的鄰點處接收1權(quán)并且從與它相關(guān)聯(lián)的面處接收2權(quán)。

R3 每一個3度點v

R4 每一個有一個1度鄰點的4度點v和每一個有兩個1度鄰點的5度點v。

根據(jù)歐拉公式[10]，在平面圖中有如下等式

接下去我們只需證明根據(jù)上述權(quán)規(guī)則重新分配權(quán)后每一個點和每一個面的最終權(quán)至少為0，就可以得到矛盾。

根據(jù)權(quán)規(guī)則，每一個1度點從它的鄰點和與它相關(guān)聯(lián)的面處總共接收3權(quán)，每一個2度點從與它相關(guān)聯(lián)的面處總共接收2權(quán)，每一個3度點v從與它相關(guān)聯(lián)的面處接收1+dG，1（v） 權(quán)，但同時v又給它的1 度鄰點 dG，1（v） 權(quán)，每一個4度點v從與它相關(guān)聯(lián)的面處接收 dG，1（v）權(quán)，但v又給它的1度鄰點dG，1（v） 權(quán)，每一個5度點v從與它相關(guān)聯(lián)的面處接收max｛ 0，dG，1（v） -1 ｝權(quán)，但v又給它的1度鄰點dG，1（v）權(quán)。因此5--點的最終權(quán)至少為0。

當(dāng)d≥6時，一個d度點v給它的每一個1度鄰點1權(quán)，因此v的最終權(quán)至少為

接下去仍需證明每一個面的最終權(quán)至少為0。為此，我們先證明引理3。對于面f，令V（f）和E（f）分別表示與f相關(guān)聯(lián)的點的集合和與f相鄰的面的集合。令

引理3 對于任意面f，有2 A（f） +B（f） ≤2 C（f） 。

證明 我們對 C（f） 進行歸納來證明結(jié)論。如果 C（f） =0，有 A（f） =B（f） =0，不等式成立。假設(shè)C（f）＞0和e=uv∈C（f）。用G'=G/e表示把邊e收縮成一個點w之后得到的圖。令f'=f/e。因為C（f'）=C（f）- ｛e ｝，所以有 C（f'）=C（f） -1。根據(jù)歸納假設(shè)，則有2 A（f'） +B（f'） ≤2 C（f'） =2 C（f）-2。

如果 ｛u，v ｝∩A（f）=｛u ｝，則有 A（f'）=A（f）- ｛u ｝和 B（f）=B（f'）；因此 2 A（f） +B（f） ≤2 C（f） 。

因為面f有一個長度至少為21的圈，并且每一條割邊都在（lf）中計算2次，所以面f的長度（lf）≥21+2 A（f） +B（f） 。令R（f）=｛v∈V（f）：β（u）=2 ｝，則f的最終權(quán)是

根據(jù)推論2，在一個圈中最多連續(xù)出現(xiàn)R（f）中的4個點，因此我們有 R（f） ≤4「（（lf）-2 A（f）-B（f））「。因為圖G的圍長g≥21，所以 （lf）-2 A（f） -B（f） ≥21。令d（f）=（lf）-2 A（f） -B（f） ，則

如果d（f）≥26，則l（'f）≥0。

綜上，定理1成立。

［1］CZERWINSKI S，GRYTCZUKJ，ZELAZNYW.Luckylabelings ofgraphs［J］.Informa Process Lett，2009，109：1078.

［2］BARTNICKI T，BOSEKB，CZERWINSKI S，et al.Additive colorings ofplanar graphs［J］.Graphs Combin，2012，30（5）：1087.

［3］AKBARI S，GHANBARI M，MANAVIYATR，et al.On the luckvchoice number ofgraphs［J］.Graphs Combin，2013，29：157.

［4］BRANDTA，DIEMUNSCH J，JAHANBEKAMS.Luckychoice number ofplanar graphs with given girth［EB/OL］.（2015-06-01）［2016-12-21］.http://math.ucdenver.edu/sjahanbekam/Lucky.pdf，2015.

［5］STEINBERGR，TOVEYC.Planar ramseynumbers［J］.J Combin TheorySer B.1993，59（2）:288.

［6］PRZYBYLOJ，WONGT.Neighbor DistinguishingEdge Colorings Via the Combinatorial NullstellensatzRevisited［J］.J Graph Theory，2015，80（4）：299.

［7］NORINE S，WONGT，ZHUX.Circular choosabilityvia combinatorial Nullstellensatz［J］.J Graph Theory，2008，59（3）:190.

［8］HUANGP，WONGT，ZHUX.Application of polynomial method toon-line list colouringofgraphs［J］.European J Combin，2012，33（5）：872.

［9］ALONN.Combinatorial Nullestellensatz［J］.Combin Prob Comput，1999（8）：7.

［10］WESTD.Introduction tograph theory［M］.USANJ:Prentice Hall Inc，1996：318-320.

The Lucky Choice Number for Planar Graph with Girth at Least 21

BAOYiping
（College ofMathematics，Physics and Information Engineering，ZhejiangNormal University，Jinhua 321004，Zhejiang）

A lucky labeling f of a graph G is a mapping which assigns to each vertex v a positive integer f（v），so that any two adjacent vertices have distinct neighbor-sums,where the neighbor-sum of a vertex v is Sf（v）=Σu∈NG（v）f（u）.The lucky choice number of G,ηl（G），is the smallest positive integer k such that for any k-list assignment L of G，G has a lucky labeling f with f（v）∈L（v）for each vertex v.In this paper，we prove that ηl（G）is at most 3 for every planar graph G with girth at least 21.

lucky choice number；discharging method；Combinatorial Nullstellensatz

10.3969/j.issn.2095-3801.2017.05.005

O157.5

A

2095-3801（2017）05-0030-06

2017-01-05；

2017-02-13

國家自然科學(xué)基金資助項目“圖的圓環(huán)染色和分數(shù)染色”（11171310）

包一萍，女，浙江杭州人，碩士生。