完全二部圖K5,7點(diǎn)強(qiáng)可區(qū)別全染色方案探討

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

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

?

完全二部圖K5,7點(diǎn)強(qiáng)可區(qū)別全染色方案探討

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

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

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

χ

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

關(guān)鍵詞：正常全染色；完全二部圖；點(diǎn)強(qiáng)可區(qū)別全染色；點(diǎn)強(qiáng)可區(qū)別全色數(shù)

0引言

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

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的一個(gè)使用了k種顏色的點(diǎn)強(qiáng)可區(qū)別正常全染色．簡記為k-VSDTC，且稱

χ

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

在本文中設(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主要結(jié)果

引理1[9]如果2≤m

χ

vst(Km,n)≤n+3．

定理1 設(shè)K5,7為完全二部圖，則

χ

vst(K5,7)=9．

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

χ

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

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

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

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

(1)f(u1v7)=2

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

(2)f(u1v7)≠2

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

情形3 當(dāng)f(v1)=f(v2)=f(v3)=f(v4)=f(v5)=2，f(v6)=f(v7)=3時(shí)，f(uivj)∈[2,9]，不失一般性，設(shè)f(u1v1)=3，f(u1v2)=4，f(u1v3)=5，f(u1v4)=6，f(u1v5)=7，f(u1v6)=8，f(u1v7)=2，有C[u1]=[8]．因?yàn)閒(u1v1)=3，可知邊u2v1的色既不是2也不是3．由f(u2vj)∈[2,9]，j=1,2,…,7，不失一般性，可設(shè)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，此時(shí)無論邊u4vj如何染以顏色，均導(dǎo)致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的另一種點(diǎn)強(qiáng)可區(qū)別全染色的方案．

圖1　K5,7的點(diǎn)強(qiáng)可區(qū)別全染色方案1

圖2　K5,7的點(diǎn)強(qiáng)可區(qū)別全染色方案2

3結(jié)語

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

χ

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

χ

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

參考文獻(xiàn)：

[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的點(diǎn)強(qiáng)可區(qū)別全染色[J]. 西南大學(xué)學(xué)報(bào)(自然科學(xué)版), 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的點(diǎn)強(qiáng)可區(qū)別全染色[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識, 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]張忠輔, 陳祥恩, 李敬文, 等. 關(guān)于圖的鄰點(diǎn)可區(qū)別全染色[J]. 中國科學(xué):A輯數(shù)學(xué), 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]陳祥恩,王治文,趙飛虎,等. 若干強(qiáng)積圖及合成圖的鄰點(diǎn)可區(qū)別一般邊染色[J]. 山東大學(xué)學(xué)報(bào)(理學(xué)版), 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]劉信生,王志強(qiáng),蘇旺輝. 圖的鄰點(diǎn)可區(qū)別VI-全色數(shù)的一個(gè)上界[J]. 蘭州大學(xué)學(xué)報(bào)(自然科學(xué)版), 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]胡志濤. 圖的點(diǎn)強(qiáng)可區(qū)別全染色的研究[D]. 蘭州:西北師范大學(xué), 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

文獻(xiàn)標(biāo)識碼：A

doi:10.7511/dllgxb201603014

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

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

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

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