路的積圖的無圈染色

董新芳，田雙亮，劉睿琳

(西北民族大學(xué) 數(shù)學(xué)與計算科學(xué)學(xué)院，甘肅 蘭州 730030)

路的積圖的無圈染色

董新芳，田雙亮*，劉睿琳

(西北民族大學(xué) 數(shù)學(xué)與計算科學(xué)學(xué)院，甘肅 蘭州 730030)

研究路的兩類積圖直積與半強(qiáng)積的無圈染色，并給出了兩個路的直積和半強(qiáng)積的無圈染色數(shù).

路；無圈染色；直積圖；半強(qiáng)積圖；無圈染色

0 引言

設(shè)G是具有頂點集V(G)與邊集E(G)的簡單連通圖,并用Δ(G)表示G的最大度.1973年Grünbaum在文獻(xiàn)[1]中提出了無圈染色概念.圖的無圈染色是指圖G中不含有2-色圈的正常點染色，所用最少的顏色數(shù)記為a(G)，并提出了關(guān)于平面圖無圈染色的猜想：每個平面圖都是無圈5-可染的.1979年，Borodin在文獻(xiàn)[2]中證明了這個猜想，同時還證明了在這個上界是可達(dá)的.1991年，Alon對一般圖類無圈染色數(shù)的上界進(jìn)行了深入研究，利用貪心算法證明了任意圖G，有a(G)≤Δ2(G)+1[3].Gerke等人在無圈染色基礎(chǔ)上，于2002年在文獻(xiàn)中提出了更一般的無圈染色概念——廣義無圈染色[4]，并給出了最大度為d的圖的廣義無圈染色數(shù)的上界.更多有關(guān)無圈染色的結(jié)果詳見文獻(xiàn)[5-8].

根據(jù)無圈染色定義，顯然有以下兩個引理：

引理1.1 對G的任意子圖H，有a(H)≤a(G).

引理1.2 設(shè)圖G有1個連通分支G1，G2，…，G1，則a(G)=max{a(Gi)|i=1,2,…，1}.

關(guān)于圖的直積與半強(qiáng)積的概念具體如下：

定義1.1[4]G和H的直積是指具有頂點集V(G)×V(H)的圖G∧H，其中(u,v)與(u＇,v＇)相鄰當(dāng)且僅當(dāng)uu＇∈E(G)且vv＇∈E(H)．

由圖的直積定義，顯然，Δ(G∧H)=Δ(G)·Δ(H)，G∧H≌H∧G.

定義1.2[4]G和H的半強(qiáng)積是指具有頂點集V(G)×V(H)的圖G·H，其中(u,v)與(u＇,v＇)相鄰當(dāng)且僅當(dāng)或者uu＇∈E(G)且vv＇∈E(H)，或者u=u＇且vv＇∈E(H)．

由圖的半強(qiáng)積定義，顯然，

Δ(G·H)=Δ(G)·Δ(H)+Δ(H)，G·H=(G∧H)∪(N∧H),

其中N∧H表示N與H的笛卡爾積，N是具有頂點集V(G)的空圖.

本文主要研究兩個路的直積與半強(qiáng)積的無圈點染色.為簡化表示，文中用(z)k表示zmodk，其中z為整數(shù)，k為正整數(shù)，并用Vc表示圖中染顏色c的頂點集合.文中未說明的術(shù)語和符號見文獻(xiàn)[9].

1 主要結(jié)論及其證明

設(shè)Pm與Pn分別為m階和n階的路，其中m,n≥2，并設(shè)Pm與Pn的頂點集分別為V(Pm)={0,1,…，m-1},V(Pn)={0,1,…，n-1}.

為研究兩個路的直積的無圈染色，首先給出以下引理：

由引理2.1知，2-維網(wǎng)格的無圈染色數(shù)不超過3.關(guān)于路的直積的無圈染色，有以下結(jié)果：

定理2.1 設(shè)n≥m≥2.若m=2，則a(Pm∧Pn)=2，否則，a(Pm∧Pn)=3.

證明 當(dāng)m=2時，因Pm∧Pn是由兩條不相交的路構(gòu)成，所以a(Pm∧Pn)=2.

當(dāng)m≥3時，因Pm∧Pn的連通分支均為2-維網(wǎng)格的子圖，由引理1.1、引理1.2與引理2.1知，a(Pm∧Pn)≤3. 又因當(dāng)m,n≥3時，Pm∧Pn中至少有一個4階圈，所以a(Pm∧Pn)>2.因此,a(Pm∧Pn)=3.

關(guān)于路的半強(qiáng)積的無圈染色有以下結(jié)果：

定理1.2 若m=2且n=3,或n=2，則a(Pm·Pn) =3，否則，a(Pm·Pn) =4.

證明 分以下兩種情況討論：

情況1m=2且n=3，或n=2.當(dāng)m=2且n=3時，因P2·Pn中含有4-階圈，所以a(P2·P3)≥3，因此僅需給出P2·P3的3-無圈染色. 令

σ(0,0)=σ(2,0)=σ(0,1)=σ(2,1)=0,σ(1, 0)=1,σ(1,1)=2.

容易驗證，σ是P2·P3的3-無圈染色.

當(dāng)n=2時，因Pm·P2中含有4-階圈，所以a(Pm·P2)≥3，因此僅需給出Pm·P2的一個3-無圈染色.

對x=0,1,y=0,1,…，m-1，令σ(0,y)=0，σ(1,y)=1+(y)2.顯然，σ所用顏色數(shù)為3.

首先，證明σ是Pm·P2的正常染色. 對Pm·P2的任意點(x,y)，其中x=0,1,y=0,1,…，m-1，根據(jù)σ的定義，σ(0,y)=0，且頂點(0,y)的3個可能鄰點所染顏色為

σ(1,y+1)=1+(y+1)2,σ(1,y)=1+(y)2,σ(1,y-1)=1+(y-1)2.

顯然，(0,y)的顏色與其鄰點的顏色不同. 類似地，σ(1,y)=1+(y)2，且頂點(1,y)的3個可能鄰點的顏色為σ(0,y+1)=σ(0,y)=σ(0,y-1)=0.顯然(1,y)的顏色與其鄰點的顏色不相同.由以上分析知，σ是Pm·P2的正常染色.

其次，說明σ是無圈的. 因染{0,1,2}中任意兩種顏色的頂點在Pm·P2中的導(dǎo)出子圖要么是路，要么為空圖，所以σ是無圈的.

綜上所述，σ是Pm·P2的3-無圈染色，因此a(Pm·P2)=3.

情況2m=2且n≥4，或m,n≥3. 考慮以下兩種子情況：

情況2.1m=2且n≥4時，可以證明a(P2·Pn)>3. 事實上，假設(shè)a(P2·Pn)≤3. 取σ是P2·Pn的3-無圈染色，所用顏色集合為{a,b,c}，則對1≤x≤n-2，有σ(x,0)≠σ(x,1). 否則，存在1≤x0≤n-2，使得σ(x0,0)=σ(x0,1).不妨設(shè)σ(x0,0)=a，因σ是無圈染色,所以頂點(x0-1,0)與(x0-1,1)染不同的顏色.不妨設(shè)σ(x0-1,0)=b,σ(x0-1,1)=c，則σ(x0+1,1)=b或c. 此時形成顏色a,b的2-色圈或顏色a,c的2-色圈， 這與σ是無圈的推論相矛盾.

在P2·Pn中，因n≥4， 所以有σ(1,0)≠σ(1,1),σ(2,0)≠σ(2,1),而σ(1,0)?{σ(2,0),σ(2,1)},σ(1,1)?{σ(2,0),σ(2,1)}，所以4個頂點(1,0)、(2,0)、(1,1)、(2,1)在σ下染不同的顏色，即所需顏色數(shù)至少為4. 這與σ是3-無圈染色矛盾. 因此，a(P2·Pn) ≥4.

現(xiàn)在證明a(P2·Pn) ≤4，即需給出P2·Pn的一個4-無圈染色. 對x=0,1,…,n-1,y=0,1,令a(x,y)=(2x+y)4.顯然，σ所用顏色數(shù)為4.

對P2·Pn的任意點(x,y)，其中x=0,1,…，n-1,y=0,1,根據(jù)σ的定義，σ(x,0)=(2x)4，且頂點(x,0)的4個可能鄰點所染顏色為σ(x-1,0) =σ(x+1,0)=(2x+2)4,σ(x-1,1)=σ(x+1,1)=(2x+3)4.

顯然，(x,0)的顏色與其鄰點的顏色不同. 類似地，σ(x,1)=(2x+1)4,且頂點(x,1)的4個可能鄰點的顏色分別為σ(x-1,1)=σ(x+1,1)=(2x+3)4,σ(x-1,0)=σ(x+1,0)=(2x+2)4.

顯然(x,1)的顏色與其鄰點的顏色不相同.由以上分析知，σ是Pm·P2的正常染色.

注意到，V0∪V2,V1∪V3,V0∪V3,V1∪V2分別在P2·Pn中的導(dǎo)出子圖均為路，V2∪V3，V0∪V1分別在P2·Pn中的導(dǎo)出子圖均為空圖.因此，σ是無圈的.

由以上分析可知，σ是P2·Pn的4-無圈點染色.

情況2.2m,n≥3，則a(Pm·Pn)>3. 否則，假設(shè)a(Pm·Pn)≤3，令σ為Pm·Pn是3-無圈點染色. 由情況2.1中討論知，σ(1,0)≠σ(1,1)，σ(1,1)≠σ(1,2)，顯然σ(1,0)≠σ(1,2).否則，σ(0,1) ?{σ(0,1),σ(1,1),σ(1,2)}.不失一般性，假設(shè)顏色集合為{a,b,c}，且σ(1,0)=σ(1,2)=a,σ(1,1)=b，則σ(0,1)=σ(2,1)=c.此時Pm·Pn中包含頂點為(1,0)、(2,1)、 (1,2)、(0,1)的一個2-色圈，這與σ是無圈相矛盾的. 因此，a(Pm·Pn)>3.

欲證a(Pm·Pn)≤4，僅需給出Pm·Pn的一個4-無圈點染色. 對0≤x≤n-1，0≤y≤m-1，令σ(x,y)=(2x+y)4.顯然，σ所用顏色數(shù)為4.

首先證明σ是Pm·Pn的正常點染色.對于任意頂點(x,y) ∈V(Pm·Pn)，其所有可能的鄰點共有6個，它們所染顏色分別為

σ(x,y)=(2x+y)4,

σ(x+1,y+1)=(2x+y+3)4,σ(x+1,y)=(2x+y+2)4,

σ(x+1,y-1)=(2x+y+1)4,σ(x-1,y-1)=(2x+y-3)4,

σ(x-1,y)=(2x+y-2)4,σ(x-1,y+1)=(2x+y-1)4.

容易驗證(x,y)的顏色與其所有可能鄰點的顏色不同，所以σ是Pm·Pn的正常點染色.

現(xiàn)在證明σ是無圈的.為討論方便，不妨假設(shè)m,n充分大.任取兩種不同顏色c1,c2∈{0,1,2,3}.并設(shè)頂點u={x,y}與v=(x＇，y＇)分別染顏色c1,c2.不妨設(shè)x＇>x，此時，x＇=x+1,y＇=y，或x＇=x+1且y＇=y+1或x＇=x+1且y＇=y-1.

當(dāng)x＇=x+1，y＇=y時，根據(jù)σ的定義，則v的不同于u的5個鄰點中，僅有頂點v1=(x+2,y)染顏色c1，在u的不同于v的5個頂點中，僅有u1=(x-1,y)染顏色c2.重復(fù)以上過程，染顏色c1與c2的頂點形成了一條路(見圖1(1))，所以Vc1∪Vc2在Pm·Pn中的導(dǎo)出子圖是無圈的.

當(dāng)x＇=x+1,y＇=y+1,時，根據(jù)σ的定義，則v的不同于u的5個鄰點中，僅有頂點v1=(x+2,y)染顏色c1.在u的不同于v的5個頂點中，僅有u1=(x-1,y+1)染顏色c2.重復(fù)以上過程，染顏色c1與c2的頂點形成了一條路(見圖1(2))，所以Vc1∪Vc2在Pm·Pn中的導(dǎo)出子圖是無圈的.

(1)x＇=x+1,y＇=y(2)x＇=x+1,y＇=y+1

圖1Vc1∪Vc2在Pm·Pn中的導(dǎo)出子圖(粗線部分)

類似地，當(dāng)x＇=x+1且y＇=y-1時，根據(jù)σ的定義，則v的不同于u的5個鄰點中，僅有頂點v1=(x+2,y)染顏色c1.在u的不同于v的5個頂點中，僅有u1=(x-1,y-1)染顏色c2，重復(fù)以上過程，染顏色c1與c2的頂點形成了類似于圖1(2)的一條路，所以Vc1∪Vc2在Pm·Pn中的導(dǎo)出子圖是無圈的.

由以上分析知，σ是無圈的，因此σ是Pm·Pn的4-無圈點染色.

[1]GrünbaumB.Acycliccoloringsofplanargraphs[J].IsraelJournalofmathematics, 1973, 14: 390-408.

[2]BorodinOV.Onacycliccoloringsofplanargraphs[J].DiscreteMathematics，1979,25: 211-236.

[3]AlonN,McDiarmidC,ReedB.Acycliccolouringofgraphs[J].RandomStructuresAlgorithms,1991, 2(3): 277-288.

[4]GreenhillC,PikhurkoO.Boundsonthegeneralizedacyclicchromaticnumbersofbounddegreegraphs[J].GraphsandConbinatorics,2005,21:407-419.

[5]FertinG,GodardE,RaspaudA.Acyclicandk-distancecoloringofthegrid[J].InformationProcessingLetters, 2003, 87:51-58.

[6]FiamcikǐI(xiàn).Theacyclicchromaticclassofagraph[J].Math.Slovac,1978, 28: 139-145.

[7]SkulrattanakulchaiS.Acycliccoloringsofsubcubicgraphs[J].InformationProcessingLetters, 2004,92: 161-167.

[8]LyonsA．Acyclicandstarcoloringsofcographs[J]．DiscreteAppliedMathematics, 2011, 159: 1842-1850．

[9]BondyJA,MurtyUSR.GraphtheorywithApplications[M].NewYork:theMacmillanpressLtd, 1976.

Product Graphs Acyclic Coloring of Path

DONG Xin-fang, TIAN Shuang-liang, LIU Rui-lin

(Mathematics and Computer Science College，Northwest University for Nationalities，Lanzhou 730030, China)

In this paper, we studied the simple graph of the direct product graph and semi strong product acyclic coloring and minimum chromatic number (markeda(G)). Using graph decomposition, construct dyeing method, given with path and path, path and cycle direct product of graphs and semi strong product graphs of acyclic chromatic number.

Acyclic coloring; Direct product graphs; Semi strong product graphs

2016-11-10

國家民委科研項目(14XBZ018)；甘肅省自然科學(xué)基金(145RJZA158)；西北民族大學(xué)中央高校基本科研業(yè)務(wù)費專項資金資助研究生項目(Yxm2015180、Yxm2015182)；西北民族大學(xué)中央高?；究蒲袠I(yè)務(wù)費專項資金項目(31920160064).

*

董新芳(1986—)，女，甘肅蘭州人，碩士研究生，主要從事組合數(shù)學(xué)與圖論方面的研究.

O157.5

A

1009-2102(2016)04-0001-04