直積圖Cm×Cn的多彩染色問題

張家嬌，吳宜均

（天津師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，天津300387）

1 引言和預(yù)備知識(shí)

圖的染色理論源于四色問題，圖的染色理論在離散數(shù)學(xué)中具有重要的地位，其在交通規(guī)劃、網(wǎng)絡(luò)通信和經(jīng)濟(jì)分析等方面有廣泛的應(yīng)用.

設(shè)G為一個(gè)簡(jiǎn)單圖，分別用E（G）和V（G）表示圖G的邊集合和頂點(diǎn)集合.對(duì)于任意頂點(diǎn)v∈V（G），用NG（v）表示圖G中與頂點(diǎn)v相鄰的頂點(diǎn)集合，定義|NG（v）|為頂點(diǎn)的度，記為 d（v）.Δ（G）=max{d（v），v∈G}定義為圖G的最大度.圖G的正常點(diǎn)染色是一個(gè)映射 c：V（G）→{1，2，…，k}，滿足任意 2 個(gè)相鄰的頂點(diǎn) u、v∈V（G）染不同的顏色，即 c（u）≠c（v）.文獻(xiàn)[1]提出了圖的動(dòng)態(tài)染色的概念，圖G的動(dòng)態(tài)染色是一個(gè)正常點(diǎn)染色 c，滿足對(duì)任意頂點(diǎn) v∈V（G），若 d（v）≥2，則c（|NG（v）|）≥2，使圖G存在動(dòng)態(tài)染色的最小色數(shù)k稱為圖G的動(dòng)態(tài)色數(shù)，記為χ2（G）.之后許多學(xué)者對(duì)動(dòng)態(tài)染色進(jìn)行了研究.文獻(xiàn)[2]證明了除C5外，對(duì)于所有的平面圖都有χ2（G）≤4；文獻(xiàn)[3]研究了動(dòng)態(tài)色數(shù)的上界；文獻(xiàn)[4]定義了圖的列表動(dòng)態(tài)染色，并研究了圖的動(dòng)態(tài)染色與列表動(dòng)態(tài)染色的關(guān)系；文獻(xiàn)[5]給出了一些特殊圖的動(dòng)態(tài)色數(shù)的上界；文獻(xiàn)[6]研究了χ2（G）與χ2（G-e）的差，及χ2（G）與χ2（G-v）的差，其中e∈E（G），v∈V（G）；文獻(xiàn)[7]研究了圖的色數(shù)與動(dòng)態(tài)色數(shù)差的上確界.

圖G的一個(gè)r-多彩染色是一個(gè)正常的頂點(diǎn)染色，使得對(duì)于任意頂點(diǎn)v∈V（G），并且d（v）≥2，有c（|NG（v）|）≥min{d（v），r}，使得圖G有r-多彩染色的最小的整數(shù)k稱為圖G的r-多彩色數(shù)，用χr（G）表示.顯然2-多彩染色即為動(dòng)態(tài)染色.文獻(xiàn)[8]證明了若平面圖G的圍長(zhǎng)不小于6，則有χr（G）≤r+5；文獻(xiàn)[9]研究了沒有K4-圖子式的圖的r-多彩染色；文獻(xiàn)[10]研究了列表3-動(dòng)態(tài)染色與圖的最大平均度的關(guān)系.

對(duì)于給定的圖G和H，直積圖G×H=（V，E），其中：

顯然有 Δ（G×H）= Δ（G）Δ（H）.本文研究圈和圈的直積圖的多彩染色.

文獻(xiàn)[1]定義了圖 Gm，n=（Vm，n，Em，n），其中點(diǎn)集和邊集分別為

在此定義的基礎(chǔ)上，當(dāng)n是奇數(shù)時(shí)，直積圖Pm×Cn與Gm，2n同構(gòu)，同構(gòu)的對(duì)應(yīng)關(guān)系為

當(dāng)n是偶數(shù)時(shí)，直積圖Pm×Cn與2Gm，n同構(gòu).

在直積圖Pm×Cn中加入邊集合F={（m，j）（1，j′）|j′≡j± 1（mod n）}，即可得到直積圖 Cm× Cn，進(jìn)而將邊集合 g（F）加到 Gm，2n中，則可得到 Cm× Cn的同構(gòu)圖.

定義圖，其中：

并且當(dāng) n為奇數(shù)時(shí)，令Sm，2n=g（F）；當(dāng) n為偶數(shù)時(shí)，令2Sm，2n=g（F）.則有

所以，當(dāng)n是奇數(shù)時(shí)，；當(dāng)n是偶數(shù)時(shí)，.圖1（a）為直積圖C4×C7，圖1（b）為與 C4× C7同構(gòu)的圖.

圖1 直積圖C4×C7和與其同構(gòu)的圖4，14Fig.1 Direct product C4 × C7and its isomorphic graph 4，14

2 Cm×Cn的多彩染色

定理1設(shè)m、n為不小于3的正整數(shù)，則有

證明 情況1n是偶數(shù).

當(dāng)n=6k時(shí)，根據(jù)多彩染色的定義，|c（NG（v））|≥min{d（v），r}，因此|c（V（G））|≥χr（G）≥min{Δ（G），r}+1，所以有χ2（Cm×Cn）≥3.

Cm和 Cn是 2 個(gè)簡(jiǎn)單圖，Cn的最小度 δ（Cn）=2，設(shè)Cn的r-多彩染色為c1，對(duì)于直積圖Cm×Cn，可定義Cm×Cn的r-多彩染色c（（u，v））=c1（u），u∈Cm，v∈Cn，易證，因此.因?yàn)棣?（C6k）=3，所以有χ2（Cm×C6k）≤χ2（C6k）=3.綜上，當(dāng)n=6k時(shí)，有χ2（Cm×Cn）=3.

當(dāng)n=6k+2或n=6k+4時(shí)，有3≤χ2（Cm×Cn）≤4.事實(shí)上，Cm×Cn中任意2個(gè)相鄰的頂點(diǎn)都在一個(gè)4-圈中，因此可得χ2（Cm×Cn）≥4.故此時(shí)有χ2（Cm×Cn）=4.

情況2n是奇數(shù).

當(dāng)n是奇數(shù)時(shí)，根據(jù)預(yù)備知識(shí)，有Cm×Cn同構(gòu)于，而的 2-多彩色數(shù)的證明方法與情況 1 一致.

定理2設(shè)m為不小于3的正整數(shù)，則有

證明因?yàn)棣ぃ–m×C4）=4，根據(jù)|c（V（G））|≥χr（G）≥r+1，有 χ3（Cm× C4）≥4.

使用反證法.假設(shè)χ3（Cm×C4）=4.由預(yù)備知識(shí)知Cm×C4同構(gòu)于，因此需求出的具體數(shù)值.

（1）如果 c（u1，v1）=1，c（u2，v4）=2，c（u2，v2）=3，c（um，v2）=4 或 c（um，v4）=4，那么 c（u1，v3）=1，c（u3，v1）≠c（u3，v3），并且 c（u3，v1）、c（u3，v3）?{1，2，3}，因此（u2，v2）不滿足 3-多彩染色的條件.

（2）如果 c（u1，v1）=1，c（u2，v4）=2，c（um，v2）=3，c（um，v4）=4，那么 c（u1，v3）=1，c（u3，v1）≠c（u3，v3），并且 c（u3，v1）、c（u3，v3）?{1，2}，不失一般性，假設(shè) c（u3，v1）=3，c（u3，v3）=4，那么 c（u2，v2）=2，并且 c（u4，v2）≠c（u4，v4），c（u4，v2）、c（u4，v4）?{2，3，4}，因此（u3，v3）不滿足3-多彩染色的條件.

（3）如果 c（u1，v1）=1，c（u2，v2）=2，c（um，v2）=3，c（um，v4）=4，那么 c（u1，v3）=1，不失一般性，設(shè) c（u3，v1）=3，c（u3，v3）=4，那么 c（u2，v4）=2，c（u4，v2）≠c（u4，v4），并且 c（u4，v2）、c（u4，v4）?{2，3，4}，因此（u3，v3）不滿足3-多彩染色的條件.

綜上，4種顏色不能使圖滿足3-多彩染色，因此有.

當(dāng)m≠4，且m為偶數(shù)時(shí)，下面給出G~m，4的一個(gè)用5種顏色的3-多彩染色c.

圖2為的染色 c的前 18 行，根據(jù)圖的特征，只需要將第6行到第13行的染色方法向后復(fù)制，如果有必要?jiǎng)h去若干行，便得到圖的5種顏色的染色.在這個(gè)染色中，有|c（N（ui，vj））|=3，滿足3-多彩條件，因此有.綜上有.

圖2 圖m，4的前18行的3-多彩染色Fig.2 First 18 lines of 3-hued coloring ofm，4

當(dāng)m≠4，且m為奇數(shù)時(shí)，的3-多彩染色與上述染色相同.因此.

當(dāng)m=4時(shí)，假設(shè)，不失一般性，如果c（u1，v1）=1，頂點(diǎn)（u1，v1）的鄰點(diǎn)必須染有至少 3 種不同的顏色，而頂點(diǎn)（u1，v1）、（u3，v1）、（u1，v3）有相同的鄰點(diǎn)集合，因此頂點(diǎn)（u3，v1）和頂點(diǎn)（u1，v3）的可用顏色數(shù)至多為2種，并且顏色1一定屬于頂點(diǎn)（u3，v1）和頂點(diǎn)（u1，v3）的可用顏色集合.因此頂點(diǎn)（u2，v2）不能滿足 3-多彩條件，于是有.圖3給出了的一個(gè)用6種顏色的染色，在這個(gè)染色中，任意相鄰2點(diǎn)的顏色不同，且|c（N（ui，vj））|=3，滿足3-多彩條件，因此.綜上有.

圖3 圖4，4的3-多彩染色Fig.3 3-hued coloring of4，4

[1]MONTGOMERY B.Dynamic Coloring of Graphs[D].Morgantown：West Virginia University，2001.

[2]LAI H J，MONTGOMERY B，POON H.Upper bounds of dynamic chromatic number[J].Ars Combinatoria，2008，68（1）：193-201.

[3]丁超，樊鎖海，賴宏建.圖的條件染色的上界[J].暨南大學(xué)學(xué)報(bào)（自然科學(xué)版），2008，29（1）：7-14.DING C，F(xiàn)AN S H，LAI H J.Upper bound on conditional chromatic number of graphs[J].Journal of Jinan University（Natural Science），2008，29（1）：7-14（in Chinese）.

[4]KIM S J，SANG J L，PARK W J.Dynamic coloring and list dynamic coloring of planar graphs[J].Discrete Applied Mathematics，2013，161（13/14）：2207-2212.

[5]KIM B M，SONG B C，RHO Y.2-distance colorings of some direct products of paths and cycles[J].Discrete Mathematics，2014，338（10）：1730-1739.

[6]MIAO L Y，LAI H J，GUO Y F.Element deletion changes in dynamic coloringofgraphs[J].DiscreteMathematics，2016，339（5）：1600-1604.

[7]郭燕芳.關(guān)于圖的動(dòng)態(tài)染色的研究[D].徐州：中國(guó)礦業(yè)大學(xué)，2016.GUO Y F.The Study of the Dynamic Coloring of Graphs[D].Xuzhou：China University of Mining and Technology，2016（in Chinese）.

[8]SONG H M，LAI H J，WU J L.On r-hued coloring of planar graphs with girth at least 6[J].Discrete Applied Mathematics，2016，164（2）：251-263.

[9]SONG H，F(xiàn)AN S，CHEN Y，et al.On r-hued coloring of K4-minor free graphs[J].Discrete Mathematics，2014，315（1）：47-52.

[10]KIM S J，PARK B.List 3-dynamic coloring of graphs with small maximumaveragedegree[J].DiscreteMathematics，2017，arXiv：1609.05824.