完全二部圖K5,7點強可區(qū)別全染色方案探討

王 蓓 蓓，　祁 麗 娟，　劉 信 生，　陳 祥 恩

( 1.西北師范大學 數(shù)學與統(tǒng)計學院, 甘肅 蘭州　730070；2.蘭州工業(yè)學院 基礎學科部, 甘肅 蘭州　730050 )

?

完全二部圖K5,7點強可區(qū)別全染色方案探討

王 蓓 蓓1，祁 麗 娟*2，劉 信 生1，陳 祥 恩1

( 1.西北師范大學 數(shù)學與統(tǒng)計學院, 甘肅 蘭州730070；2.蘭州工業(yè)學院 基礎學科部, 甘肅 蘭州730050 )

摘要：利用組合分析的方法先討論了完全二部圖K5,7的點強可區(qū)別全染色，在此基礎之上給出了兩種具體的關于完全二部圖K5,7的點強可區(qū)別全染色方案．此結果的給出不僅確定了完全二部圖K5,7的點強可區(qū)別全色數(shù)為9，而且對于胡志濤所提出的關于完全二部圖的點強可區(qū)別全染色的猜想：“如果m≥4且n<2m-2時，那么

χ

vst(Km,n)=n+3”中當m=5時作出了否定，從而進一步確定了此猜想成立的范圍．

關鍵詞：正常全染色；完全二部圖；點強可區(qū)別全染色；點強可區(qū)別全色數(shù)

0引言

圖染色的基本問題就是確定其各種染色法的色數(shù)．圖的染色問題一直是圖論研究的重要問題之一，具有重要的理論和實際意義．現(xiàn)實生活中的許多領域都會涉及圖的著色，如任務分配問題、排課表問題、存儲問題、交通定向問題等．所以染色問題一直是圖論研究領域較為活躍的一部分．文獻[1]中，Zhang等提出了鄰點強可區(qū)別全染色的概念，并研究討論了完全二部圖的鄰點強可區(qū)別全染色．在文獻[2]中胡志濤等通過對圖的鄰點強可區(qū)別全染色的要求加強之后提出了圖的點強可區(qū)別正常全染色，并研究了完全二部圖K4,n(n>4)的點強可區(qū)別全染色；文獻[3-4]研究了當1≤m≤3時的完全二部圖Km,n(m≤n)的點強可區(qū)別全染色；文獻[5-8]給出了一些相關染色的結果．本文討論完全二部圖K5,7的點強可區(qū)別全色數(shù)的確切值，以進一步拓寬圖的染色理論的應用范圍．

1定義

若：(i)對任意uv，uw∈E，v≠w，有f(uv)≠f(uw)；

(ii)對任意uv∈E，f(u)≠f(v)，有f(u)≠f(uv)，f(v)≠f(uv)；

(iii)對任意u，v∈V，u≠v，有C[u]≠C[v]

那么稱f是圖G的一個使用了k種顏色的點強可區(qū)別正常全染色．簡記為k-VSDTC，且稱

χ

vst(G)=min {k|G存在k-VSDTC}為G的點強可區(qū)別全色數(shù)．

在本文中設V(K5,7)={u1,u2,…,u5，v1，v2,…,v7}，E(K5,7)={uivj|i=1,2,…,5，j=1,2,…,7}．并且為了表示和敘述的簡潔，用[n,m]表示集合{n,n+1,n+2,…,m}，用[n]表示集合{1,2,…,n}．

2主要結果

引理1[9]如果2≤m

χ

vst(Km,n)≤n+3．

定理1 設K5,7為完全二部圖，則

χ

vst(K5,7)=9．

證明 由引理1可以看出9≤

χ

vst(K5,7)≤10．下面探討使用9種色的K5,7點強可區(qū)別全染色是否存在，如果存在，有哪些染色方案．

假設K5,7有一使用了顏色1、2、3、4、5、6、7、8、9的9-VSDTCf，設在本文的染色過程中，點ui(i=1,2,…,5)均染以顏色1，進而根據(jù)點vj(j=1,2,…,7)的染色分以下情形討論：

情形1 當f(v1)=f(v2)=f(v3)=f(v4)=f(v5)=f(v6)=f(v7)=2時，f(uivj)∈[3,9]，i=1,2,…,5，j=1,2,…,7，此時無論邊f(xié)(uivj) 如何染以顏色均導致C[ui]及C[vj]不可區(qū)別，矛盾．

情形2 當f(v1)=f(v2)=f(v3)=f(v4)=f(v5)=f(v6)=2，f(v7)=3時，f(uivj)∈[2,9]，不失一般性，設f(u1v1)=3，則f(u1vj)∈{2，4,5,6,7，8,9}，j=2,3,…,7．因為f(vj)=2，j=1,2,…,6，可知邊u1v7的色是2，或者任意一條邊的色都不是2，據(jù)此再分以下兩種情形討論：

(1)f(u1v7)=2

由f(u1vj)∈[4,9]，j=2,3,…,6．不失一般性，設f(u1v2)=4，f(u1v3)=5，f(u1v4)=6，f(u1v5)=7，f(u1v6)=8，有C[u1]=[8]，此時點u1的強色集合已被確定．又因為f(u1v1)=3且f(u2)=1，f(v1)=2，所以邊u2v1的色不是3．由f(u2v1)∈[4,9]，不失一般性，可設f(u2v1)=4，同理可知，邊u2v2的色不是4，邊u2v3的色不是5，邊u2v4的色不是6，邊u2v5的色不是7，邊u2v6的色不是8，邊u2v7的色不是2．由f(u2vj)∈{2,3,5,6,7，8,9}，不失一般性，可設f(u2v2)=3，f(u2v3)=6，f(u2v4)=7，f(u2v5)=8，f(u2v6)=9，f(u2v7)=5．此時C[u1]=C[u2]，即點u1、u2的強色集合不可區(qū)別，矛盾．

(2)f(u1v7)≠2

不失一般性，設f(u1v7)=9，f(u1v2)=4，f(u1v3)=5，f(u1v4)=6，f(u1v5)=7，f(u1v6)=8，而此時邊u2vj無法按點強可區(qū)別的要求染以顏色，矛盾．

情形3 當f(v1)=f(v2)=f(v3)=f(v4)=f(v5)=2，f(v6)=f(v7)=3時，f(uivj)∈[2,9]，不失一般性，設f(u1v1)=3，f(u1v2)=4，f(u1v3)=5，f(u1v4)=6，f(u1v5)=7，f(u1v6)=8，f(u1v7)=2，有C[u1]=[8]．因為f(u1v1)=3，可知邊u2v1的色既不是2也不是3．由f(u2vj)∈[2,9]，j=1,2,…,7，不失一般性，可設f(u2v1)=4，f(u2v4)=7，f(u2v5)=3，f(u2v6)=2，f(u2v7)=9，可知C[u2]={1,2,3，4,5,6,7,9}，且C[u1]=C[u2]．由f(u1v7)=f(u2v6)=2且f(vj)=2，j=1,2,…,5，所以f(u3vj)∈[3,9]，j=1,2,…,7．同理，f(u4vj)∈[3,9]，j=1,2,…,7，此時無論邊u4vj如何染以顏色，均導致C[u3]=C[u4]，矛盾．

(1)f(u4v4)=2

(2)f(u4v4)≠2

①f(u5v4)≠2

②f(u5v4)=2

所以

χ

vst(K5,7)=9．

除了圖1所給出的染色方案，圖2給出了完全二部圖K5,7的另一種點強可區(qū)別全染色的方案．

圖1　K5,7的點強可區(qū)別全染色方案1

圖2　K5,7的點強可區(qū)別全染色方案2

3結語

本文利用組合分析法討論了完全二部圖K5,7的點強可區(qū)別全染色，并得到完全二部圖K5,7的點強可區(qū)別全色數(shù)

χ

vst(K5,7)=9，并在此基礎之上給出了兩種具體的關于完全二部圖K5,7的點強可區(qū)別全染色方案．此結果的得出直接對文獻[9]當中胡志濤提出的關于完全二部圖的點強可區(qū)別的猜想：“如果m≥4且n<2m-2時，那么

χ

vst(Km,n)=n+3”中當m=5時作出了否定，從而進一步確定了此猜想成立的范圍．此結論的得出不僅為研究Km,n(m≥4，n<2m-2)這類完全二部圖的點強可區(qū)別全染色奠定了基礎，也為研究更多類的完全二部圖Km,n的點強可區(qū)別全染色提供了思路方法．

參考文獻：

[1] ZHANG Zhong-fu, CHENG Hui, YAO Bing,etal. On the adjacent-vertex-strongly-distinguishing total coloring of graphs [J]. Science in China Series A: Mathematics, 2008, 51(3): 427-436.

[2]胡志濤,王治文,陳祥恩. 完全二部圖K4,n的點強可區(qū)別全染色[J]. 西南大學學報(自然科學版), 2013, 35(3): 64-68.

HU Zhi-tao, WANG Zhi-wen, CHEN Xiang-en. Vertex strongly distinguishing total coloring of the complete bipartite graphK4,n[J]. Journal of Southwest University (Natural Science), 2013, 35(3):64-68. (in Chinese)

[3]陳祥恩,胡志濤,王治文. 完全二部圖K1,n,K2,n和K3,n的點強可區(qū)別全染色[J]. 數(shù)學的實踐與認識, 2012, 42(11):214-218.

CHEN Xiang-en, HU Zhi-tao, WANG Zhi-wen. Vertex strongly distinguishing total coloring of the complete bipartite graphsK1,n,K2,nandK3,n[J]. Mathematics in Practice and Theory, 2012, 42(11):214-218. (in Chinese)

[4]CHEN Xiang-en, HU Zhi-tao, YAO Bing,etal. Vertex strongly distinguishing total coloring of complete bipartite graphK3,3[C] // 2012 International Conference on Systems and Informatics (ICSAI). Piscataway: IEEE, 2012:2687-2691.

[5]ZHANG Zhong-fu, Woodall D R, YAO Bing,etal. Adjacent strong edge colorings and total colorings of regular graphs [J]. Science in China Series A: Mathematics, 2009, 52(5):973-980.

[6]張忠輔, 陳祥恩, 李敬文, 等. 關于圖的鄰點可區(qū)別全染色[J]. 中國科學:A輯數(shù)學, 2004, 34(5):574-583.

ZHANG Zhong-fu, CHEN Xiang-en, LI Jing-wen,etal. On adjacent vertex distinguishing total coloring of graphs [J]. Science in China (Ser. A Mathematics), 2004, 34(5): 574-583. (in Chinese)

[7]陳祥恩,王治文,趙飛虎,等. 若干強積圖及合成圖的鄰點可區(qū)別一般邊染色[J]. 山東大學學報(理學版), 2013, 48(6):18-22.

CHEN Xiang-en, WANG Zhi-wen, ZHAO Fei-hu,etal. General neighbor-distinguishing edge coloring of strong products and compositions of graphs [J]. Journal of Shandong University (Natural Science), 2013, 48(6):18-22. (in Chinese)

[8]劉信生,王志強,蘇旺輝. 圖的鄰點可區(qū)別VI-全色數(shù)的一個上界[J]. 蘭州大學學報(自然科學版), 2011, 47(6):81-83,92.

LIU Xin-sheng, WANG Zhi-qiang, SU Wang-hui. An upper bound for the adjacent vertex-distinguishing VI-total chromatic number of graphs [J]. Journal of Lanzhou University (Natural Sciences), 2011, 47(6):81-83,92. (in Chinese)

[9]胡志濤. 圖的點強可區(qū)別全染色的研究[D]. 蘭州:西北師范大學, 2013.

HU Zhi-tao. Research on vertex strongly distinguishing total coloring of graphs [D]. Lanzhou: Northwest Normal University, 2013. (in Chinese)

Probe of schemes for vertex strongly distinguishing total coloring of complete bipartite graphK5,7

WANGBei-bei1,QILi-juan*2,LIUXin-sheng1,CHENXiang-en1

( 1.College of Mathematics and Statistics, Northwest Normal University, Lanzhou 730070, China；2.Department of Basic Sciences, Lanzhou Institute of Technology, Lanzhou 730050, China )

Abstract：Firstly, the vertex strongly distinguishing total coloring of complete bipartite graph K5,7is discussed using the method of combinatorial analysis. Then, based on the discussion, two schemes about the vertex strongly distinguishing total coloring of complete bipartite graph K5,7are put forward. The results not only help to determine the vertex strongly distinguishing total chromatic number of complete bipartite graph K5,7which is equal to nine, but also negate the conjecture proposed by Hu Zhi-tao: ″If m≥4 and n<2m-2, then

χ

vst(Km,n)=n+3″ whenm=5. Furthermore, the scope which makes this conjecture established is determined.

Key words：proper total coloring; complete bipartite graph; vertex strongly distinguishing total coloring; vertex strongly distinguishing total chromatic number

中圖分類號：O157.5

文獻標識碼：A

doi:10.7511/dllgxb201603014

作者簡介:王蓓蓓(1990-)，女，碩士生，E-mail:924174362@163.com；祁麗娟*(1972-)，女，副教授，E-mail:282455295@qq.com.

基金項目:國家自然科學基金資助項目(61163037，61163054，61363060).

收稿日期：2015-12-05；修回日期: 2016-03-20．

文章編號：1000-8608(2016)03-0309-04