張家嬌，吳宜均

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

1 引言和預備知識

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

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

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

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

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

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

在此定義的基礎上，當n是奇數(shù)時，直積圖Pm×Cn與Gm，2n同構，同構的對應關系為

當n是偶數(shù)時，直積圖Pm×Cn與2Gm，n同構.

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

定義圖，其中：

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

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

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

2 Cm×Cn的多彩染色

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

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

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

Cm和 Cn是 2 個簡單圖，Cn的最小度 δ（Cn）=2，設Cn的r-多彩染色為c1，對于直積圖Cm×Cn，可定義Cm×Cn的r-多彩染色c（（u，v））=c1（u），u∈Cm，v∈Cn，易證，因此.因為χ2（C6k）=3，所以有χ2（Cm×C6k）≤χ2（C6k）=3.綜上，當n=6k時，有χ2（Cm×Cn）=3.

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

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

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

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

證明因為Δ（Cm×C4）=4，根據(jù)|c（V（G））|≥χr（G）≥r+1，有 χ3（Cm× C4）≥4.

使用反證法.假設χ3（Cm×C4）=4.由預備知識知Cm×C4同構于，因此需求出的具體數(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}，不失一般性，假設 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，不失一般性，設 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-多彩染色，因此有.

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

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

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

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

當m=4時，假設，不失一般性，如果c（u1，v1）=1，頂點（u1，v1）的鄰點必須染有至少 3 種不同的顏色，而頂點（u1，v1）、（u3，v1）、（u1，v3）有相同的鄰點集合，因此頂點（u3，v1）和頂點（u1，v3）的可用顏色數(shù)至多為2種，并且顏色1一定屬于頂點（u3，v1）和頂點（u1，v3）的可用顏色集合.因此頂點（u2，v2）不能滿足 3-多彩條件，于是有.圖3給出了的一個用6種顏色的染色，在這個染色中，任意相鄰2點的顏色不同，且|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].暨南大學學報（自然科學版），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]郭燕芳.關于圖的動態(tài)染色的研究[D].徐州：中國礦業(yè)大學，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.