關(guān)于路的并的點(diǎn)可區(qū)別V-全染色

馬寶林,劉娟,王軍濤,丁玉榮

（河南科技學(xué)院,河南新鄉(xiāng)453003）

關(guān)于路的并的點(diǎn)可區(qū)別V-全染色

馬寶林,劉娟,王軍濤,丁玉榮

（河南科技學(xué)院,河南新鄉(xiāng)453003）

根據(jù)簡單圖的點(diǎn)可區(qū)別V-全染色的概念及其染色方法,討論了m個(gè)長度為n的路的頂點(diǎn)不交并的點(diǎn)可區(qū)別V-全染色,并給出全色數(shù)的結(jié)論及其證明,根據(jù)結(jié)論提出了相應(yīng)的猜想,為進(jìn)一步探討其他簡單圖的點(diǎn)可區(qū)別V-全染色提供了理論證據(jù),豐富了圖的點(diǎn)可區(qū)別V-全染色的結(jié)果.

簡單圖；全色數(shù)；點(diǎn)可區(qū)別V-全染色；mPn

圖的染色問題是NP完全問題,目前已得到了很多結(jié)果[1-3],2004年,張忠輔、陳祥恩等在圖的全染色的基礎(chǔ)上提出了鄰點(diǎn)可區(qū)別全染色[1],2008年,又在點(diǎn)可區(qū)別正常全染色的基礎(chǔ)上提出了圖的點(diǎn)可區(qū)別一般全染色[2].本文從簡單圖的點(diǎn)可區(qū)別V-全染色的定義出發(fā),討論mP2、mP3、mP4的點(diǎn)可區(qū)別V-全染色,給出全色數(shù)的結(jié)論及其證明,并提出了自己的猜想.

1 相關(guān)概念

在文獻(xiàn)[1]和[2]中,對于部分簡單圖的點(diǎn)可區(qū)別正常全染色已有相對完善的結(jié)果,并給出定義,圖的正常全染色是指：（1）相鄰的兩個(gè)頂點(diǎn)染色不同；（2）相鄰的兩條邊染色不同；（3）任意的點(diǎn)和與之關(guān)聯(lián)的邊染色不同,并用χvt(G)表示了圖的點(diǎn)可區(qū)別全色數(shù).如若上述（1）～（3）條件中只滿足其中一個(gè)或兩個(gè)條件時(shí)就被稱之為圖的一般全染色.本文僅考慮只滿足（2）和（3）時(shí)的情形.

定義設(shè)G是一個(gè)簡單圖,k是正整數(shù),f是V( G)∪E( G)到{1,2,3,…,k}的一個(gè)映射,對圖G的一個(gè)全染色f,用C( u)表示點(diǎn)u和它所關(guān)聯(lián)的邊所染的顏色組成的集合,即C( u)={f( u)}∪{f( uv)|uv∈E( G)}.若對于V（G）中的任意兩點(diǎn)u和v,都有C( u)≠C( v),則稱f是圖G的點(diǎn)可區(qū)別V-全染色,簡稱為圖G的VDVT染色.

圖G的一個(gè)VDVT染色所需要最少顏色的數(shù)目稱為圖G的點(diǎn)可區(qū)別V-全色數(shù),記為(G).

引理對于簡單圖G,令ni是度為i（δ≤i≤Δ）的頂點(diǎn)的個(gè)數(shù),若Kn存在μ-點(diǎn)可區(qū)別V-全染色,則有

在文獻(xiàn)[4]中圖mP2與mP3的點(diǎn)可區(qū)別E-全染色做了研究,其主要結(jié)論mP2與mP3圖的點(diǎn)可區(qū)別V-全染色基本一致,本文中部分結(jié)果證明可參閱文獻(xiàn)[4].

2 若干結(jié)論

定理1對于m條長為2的路的并的點(diǎn)可區(qū)別V-全染色,有

證明略.

定理2對于m條長為3的路的并的點(diǎn)可區(qū)別V-全染色,有

證明：當(dāng)m=1,其染色方法以頂點(diǎn)色集合的形式表現(xiàn)為：{1,2},{2,1,3},{3,1},顯然有(1P )=3；3

當(dāng)m=2,其染色方法以頂點(diǎn)色集合的形式表現(xiàn)為：{1,2},{2,1,3},{3,1}；{3,2},{2,1,4},{4,1},顯然有(2P )=4；3

當(dāng)m=3,其染色方法以頂點(diǎn)色集合的形式表現(xiàn)為：{1,2},{2,1,3},{3,1}；{3,2},{2,1,4},{4,1}；{4,3},{3,2,4}, {4,2}；顯然有(3P )=4；3

當(dāng)m≥4時(shí),染色方案參閱文獻(xiàn)[4].

定理3對于m條長為4的路的并的點(diǎn)可區(qū)別V-全染色,有當(dāng)m=1,2時(shí),(mP)=4；4

當(dāng)m=2時(shí),在前面的基礎(chǔ)上,給出其染色方法以頂點(diǎn)色集合的形式表現(xiàn)為：{1,3},{3,2,4},{4,3,1},{1,4}；{3,2},{2,4,1},{1,2,3},{3,4}；有(2P)=4；t4

當(dāng)m=3,4,5時(shí),在前面的基礎(chǔ)上,第3,4,5條路的染色方法以頂點(diǎn)色集合的形式表現(xiàn)為：{5,1},{1,2,5}, {5,3,2},{2,5}；{5,3},{3,4,5},{5,2,4},{4,5}；{2,1},{1,3,5},{5,1,4},{4,2}；顯然為VDVT全染色,且(mP)=5；4

當(dāng)m≥6時(shí),結(jié)論等價(jià)于

將本結(jié)論分4種情形討論：

定理得證．

3 一個(gè)猜想

猜想對于m條長為n的路的并的點(diǎn)可區(qū)別V-全染色,其全色數(shù)若記為(mP),則：n

其中k為一個(gè)正整數(shù)．

4 結(jié)束語

本文依據(jù)簡單圖的點(diǎn)可區(qū)別V-全染色定義,給出了m條長為n的路的并的點(diǎn)可區(qū)別V-全色數(shù),并給出了完整的證明過程,最后提出關(guān)于mPn的點(diǎn)可區(qū)別V-全染色猜想,為進(jìn)一步探討其他簡單圖的點(diǎn)可區(qū)別V-全染色提供了思想方法,豐富了圖的點(diǎn)可區(qū)別全染色的結(jié)論,為進(jìn)一步解決相關(guān)實(shí)際問題提供理論依據(jù).

[1]Zhang Z F,Chen X E.On adjacent-vertex-distinguishing total coloring of graphs[J].Science in China（Ser A）,2005,48（3）：289-299．

[2]陳祥恩.n-方體的點(diǎn)可區(qū)別全色數(shù)的漸進(jìn)性態(tài)[J].西北師范大學(xué)學(xué)報(bào)：自然科學(xué)版,2005,41（5）：1-3．

[3]張忠輔,陳祥恩,李敬文,等.關(guān)于圖的鄰點(diǎn)可區(qū)別全染色[J].中國科學(xué)A輯：數(shù)學(xué),2004,34（5）：574-583．

[4]馬寶林,劉娟,陳祥恩.圖mP2與mP3的點(diǎn)可區(qū)別E-全染色[J].讀寫算,2010（9）：201-202.

[5]Ma B L,Chen X E,Liu J.2-distance coloring of strong product of graghs[J].山東大學(xué)學(xué)報(bào),2010,45（3）：66-70.

[6]Zhang Z F,Qiu P X,Xu B G,et al．Vertex-distinguishing total colorings of graphs[J].Ars Combinatoria,2008（87）：33-45．

[7]馬寶林.完全圖的點(diǎn)可區(qū)別V-全染色[J].河南科技學(xué)院學(xué)報(bào)：自然科學(xué)版,2011,39（5）：44-46.

（責(zé)任編輯：盧奇）

Vertex distinguishing V-total chromatic number of mPn

Ma Baolin,Liu Juan,Wang Juntao,Ding Yurong
（Henan Institute of Science and Technology,Xinxiang 453003,China）

According to the definition and the method of the vertex-distinguishing V-total coloring,the vertexdistinguishing V-total coloring of the vertex-disjoint union of m paths with lengths n is discussed,and the conclusion and proof of the vertex-distinguishing V-total chromatic number are given,finally,proposed a conjecture,To further explore other simple graph vertex-distinguishing V-total coloring provides a theoretical evidence that enriched the graph vertex-distinguishing V-total coloring results．

simple graph；chromatic number；vertex-distinguishing V-total coloring；mPn

O157.5

A

1008-7516（2012）03-0065-04

10．3969/j．issn．1008-7516．2012．03．016

2012-03-08

馬寶林（1978-）,男,回族,甘肅張家川人,碩士,講師．主要從事圖論及其應(yīng)用研究．