路與路的強積的r-多彩染色

邵瑞芳，左連翠

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

1 引言和預備知識

本文考慮的圖都是連通有限的無向圖，并且沒有重邊.用[a，b]表示從a到b的所有整數(shù)，b≥a＞0.

對于圖 G=（V，E）的一個頂點染色 c：V（G）→[1，k]，如果相鄰2個頂點著不同的顏色，則這種染色稱為正常染色，使得圖G為正常染色所使用的最少色數(shù)k，稱為圖G的正常色數(shù)，用χ（G）來表示.圖G的r-多彩k-染色是一個使用k種顏色的正常染色c：V（G）→[1，k]，并且對于圖 G 中每個度為 d（v）的頂點v，滿足|c（N（v））|≥min{d（v），r}，其中 N（v）表示頂點 v的鄰點集，c（N（v））={c（u），u∈N（v）}，使得圖 G 為r-多彩k-染色的最小整數(shù)k稱為圖G的r-多彩色數(shù)，用χr（G）來表示.顯然有χ（G）≤χr（G）.

對于r-多彩染色，國內(nèi)外許多學者進行了研究.文獻[1]證明了當3|n時，χ2（Cn）=3，當n=5時，χ2（Cn）=5，其他情況χ2（Cn）=4.文獻[2]證明了如果圖G是一個強正則圖（不包含C5和完全二部圖），則χ2（G）-χ（G）≤1.文獻[3]證明了對于任意k-正則圖，有χ2（G）≤χ（G）+14.06 ln k+1.文獻[4]證明了對任何正整數(shù)n，都存在一個正常色數(shù)為n的正則圖，滿足χ2（G）-χ（G）≥1.關(guān)于圖的二元運算，文獻[5]證明了如果G和H是2個簡單圖，且 δ（G）≥2，δ（G）表示圖 G的最小度，那么有χ2（G□H）≤max{χ2（G），χ（H）}，G□H表示圖G和H的笛卡爾乘積.文獻[6]證明了對于2個簡單圖G和H，若δ（G）≥r，那么有χr（G□H）≤max{χr（G），χ（H）}.文獻[7]證明了若 mn≡2（mod 4），m × n 網(wǎng)格不存在3-多彩4-染色.文獻[8]研究了網(wǎng)格和超環(huán)面的r-多彩染色.文獻[9]證明了若G和H是2個簡單圖，并且δ（G）≥r，則χr（G×H）≤χr（G），其中G×H表示圖G和圖H的直積，同時獲得了一些圖的多彩色數(shù)的確切值.

設G和H是2個簡單圖，G和H的強積用G□H表示，其頂點集為V（G）×V（H），邊集為X∪Y∪Z，其中：

顯然.本文考慮路與路強積的r-多彩染色，并給出了其r-多彩色數(shù)的確切值.

引理1χr（G）≥min{Δ（G），r}+1，對于樹等號成立.

引理2如果r≥Δ（G），那么χr（G）=χΔ(G）（G）.

引理3χr+1（G）≥χr（G），r≥2.

2 主要結(jié)論

定理設Pm=u1u2…um和Pn=v1v2…un分別為m階和n階的路，n、m≥2，且n、m是正整數(shù)，則有如下結(jié)論.

當r≥8時，有

證明設.根據(jù)強積圖的定義，Pn和Pm滿足交換律，可以假設m≥n≥2.

首先，當 m=n=2 時，頂點（u1，v1）、（u1，v2）、（u2，v1）、（u2，v2）構(gòu)成的圖是一個K4，則χr（G）=4，r≥2.

以下設m≥3.

c是圖G的一個2-多彩染色，所以χ2（G）≤4.因此χ2（G）=4.

（2）對于，利用與（1）相同的方法，可以證明χ3（G）=χ2（G）=4.

（3）對于，由引理1，此時有χ4（G）≥5.定義如下染色c

其中c（ui+1，v5k+j）=c（ui，vp），p≡（j+3）（mod 5），p∈[1，5].c是圖G的一個4-多彩染色，所以χ4（G）≤5.因此χ4（G）=5.

（4）對于，由引理1，此時有χ5（G）≥6.

情況1n=2.能夠定義如下染色c

很明顯，c是圖G的一個5-多彩染色，所以χ5（G）≤6.因此χ5（G）=6.

情況 2n≥3.可以假設 c（u1，v1）=1，c（u1，v2）=2，c（u2，v1）=3，c（u2，v2）=4，由 r-多彩染色的定義，有 c（u1，v3）=5，c（u2，v3）=6，c（u3，v2）?[1，6]，因此χ5（G）≥7.

情況2.1n=3.定義如下染色c

其中：c（ui，v4k+j）=c（ui，vj），i=1、3，j∈[1，4]；c（u2，v3k+j）=c（u2，vj），j∈[1，4].c是圖G的一個5-多彩染色，所以χ5（G）≤7.因此，在這種情況下χ5（G）=7.

情況2.2n≥3.由情況2.1和r-多彩染色的定義，有c（u4，v1）=7，c（u4，v2）?[1，7]，所以χ5（G）≥8.定義如下染色c

其中c（ui+2，vj）=c（ui，vp），p≡（j+2）（mod 4），p∈[1，4].c是圖G的一個5-多彩染色，所以χ5（G）≤8.因此，在這種情況下χ5（G）=8.

（5）對于.

情況1n=2.此時Δ（G）=5，由引理2有χ6（G）=χ5（G）=6.

情況2n≥3.

情況2.1n=3.由引理2，此時結(jié)果與（4）情況2.1相同，因此χ6（G）=7.

情況2.2n≥4.由引理3，此時有χ6（G）≥χ5（G）=8.定義如下染色c

c是圖G的一個6-多彩染色，所以χ6（G）≤8.因此，在這種情況下.

（6）對于χ7（PnPm）.

情況1n=2.在這種情況下，Δ（G）=5，由引理2有χ7（G）=χ5（G）=6.

情況2n≥3，由引理1有χ7（G）≥8.能夠定義如下染色c

其中c（ui+3，vj）=c（ui，vp），p≡j（mod 8），p∈[1，8].c是圖G的一個7-多彩染色，所以χ7（G）≤8.因此，在這種情況下χ7（G）=8.

（7）對于，r≥8.在這種情況下，由引理2可知χr（G）=χ8（G）.

情況1n=2.在這種情況下，Δ（G）=5，由引理2有χr（G）=χ5（G）=6.

情況2n≥3.由引理1，此時有χ8（G）≥9.定義如下染色c

很明顯，c是圖G的一個r-多彩染色，所以χr（G）≤9.因此，在這種情況下χr（G）=9.

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

[2]AKBARIS，GHANBARIM，JAHANBAKEMS.Onthedynamic coloring of strongly regular graphs[J].IEEE International Conference on Systems，2011，32（14）：257-264.

[3]ALISHAHI M.On the dynamic coloring number of graphs[J].Discrete Applied Mathematics，2011，159（2/3）：152-156.

[4]ALISHAHI M.Dynamic chromatic number of regular graphs[J].Discrete Applied Mathematics，2012，160（15）：2098-2103.

[5]AKBARI S，GHANBARI M，JAHANBEKAM S.On the dynamic coloring of Cartesian product graphs[J].Ars Combinatoria，2014，114（4）：161-168.

[6]SUIL O.Edge-connectivity，Eigenvalues，and Matchings in Regular Graphs[D].Urbana：University of Illinoist，2011.

[7]KANG R，MULLER T，WEST D B.On r-dynamic coloring of gird[J].Discrete Applied Mathematics，2014，186（1）：286-290.

[8]JAHANBEKAM S，KIM J，SUIL O，et al.On r-dynamic coloring of graphs[J].Discrete Applied Mathematics，2016，206（C）：65-72.

[9]張冰.幾類圖的r-hued染色和距離標號[D].徐州：中國礦業(yè)大學，2016.ZHANGB.The r-huedColoringandDistanceLabelingofSeveralClasses of Graphs[D].Xuzhou：China University of Mining and Technology，2016（in Chinese）.