一類含有4-圈的單圈圖一般點可區別全染色

陳 祥 恩， 李 婷， 王 治 文

( 1.西北師范大學 數學與統計學院， 甘肅 蘭州 730070；2.寧夏大學 數學計算機科學學院， 寧夏 銀川 750021 )

一類含有4-圈的單圈圖一般點可區別全染色

陳 祥 恩*1， 李 婷1， 王 治 文2

( 1.西北師范大學 數學與統計學院， 甘肅 蘭州 730070；2.寧夏大學 數學計算機科學學院， 寧夏 銀川 750021 )

設G為簡單圖．設f是圖G的一個一般全染色，若對圖G的任意兩個不同的頂點u、v，有C(u)≠C(v)，則稱f為圖G的一般點可區別全染色(簡記為GVDTC)．對圖G進行一般點可區別全染色所需要的最少顏色數稱為圖G的一般點可區別全色數．將一類含有4-圈的單圈圖懸掛邊的染色按從小到大的順序排列，探討了它的一般點可區別全染色，確定了它具有一般點可區別全染色，并得到了它的一般點可區別全色數．

單圈圖；一般全染色；一般點可區別全染色；一般點可區別全色數

0 引 言

點可區別一般邊染色是由Harary等于1985年在文獻[1]中提出的，文獻[2-4]對此也進行了研究．近些年來點可區別的未必正常的全染色也逐漸被研究．例如，點可區別IE-全染色在文獻[5]中被提出，而一般點可區別全染色也在文獻[6]中被提出．本文受文獻[6]的啟發，使用更為簡單的方法探討一類含有4-圈的單圈圖的一般點可區別全染色，并得到它的一般點可區別全色數．

1 準備工作

圖G的一個一般全染色是指若干種顏色對圖G的全體頂點及邊的一個分配．

設f為圖G的一個一般全染色或IE-全染色，x為圖G的一個頂點，將在f下x的顏色及與x關聯的邊的顏色所構成的集合(非多重集)記為Cf(x)或C(x)，稱之為頂點x在f下的色集合，即C(x)={f(xu)|xu∈E}∪{f(x)}．

設f為圖G的一般全染色，若對圖G的任意兩個不同的頂點u、v，有C(u)≠C(v)，則稱f為圖G的點可區別一般全染色或者一般點可區別全染色(簡記為GVDTC)．圖G的使用了k種顏色的一般點可區別全染色稱為圖G的k-一般點可區別全染色(簡記為k-GVDTC)．對圖G進行一般點可區別全染色所需要的最少顏色數稱為圖G的一般點可區別全色數，記為χgvt(G)．

星Sn就是完全二部圖K1,n(n≥1)．稱Sm,n是雙星，如果Sm,n是樹，并且頂點集為V(Sm,n)={ui|i=0，1，…，m}∪{vj|j=0，1，…，n}，邊集為E(Sm,n)={u0ui|i=0，1，…，m}∪{v0vj|j=0，1，…，n}∪{u0v0}，其中m、n是正整數且均大于1．稱Sp，q，r是三星，如果Sp，q，r是樹，并且頂點集為V(Sp，q，r)={ui|i=0，1，…，p}∪{vj|j=0，1，…，q}∪{wt|t=0，1，…，r}，邊集為E(Sp，q，r)={u0ui|i=0，1，…，p}∪{v0vj|j=0，1，…，q}∪{w0wt|t=0，1，…，r}∪{u0v0，v0w0}，其中p、q、r是正整數且均大于1．

本文設C4；m1，m2，m3，m4表示如圖1所示的一類含有4-圈的單圈圖．

文獻[6]中研究了路、圈、星(即K1,n)、雙星、三星、輪、扇、完全圖的一般點可區別全染色，確定了它們的一般點可區別全色數．本文將探討一類含有4-圈的單圈圖C4；m1，m2，m3，m4的一般點可區別全染色，并確定它們的一般點可區別全色數．

圖1 一類含有4-圈的單圈圖

引理1[6]設Sn(n≥1)是一個星，則

χgvt(Sn)= 2；n=1，23；n=38n+1-12；n≥4ì?í??????

2 主要結果及其證明

定理1 設C4；m1，m2，m3，m4(mi≥1，i=1，2，3，4)是一個含有4-圈的單圈圖，令l=m1+m2+m3+m4，則

χgvt(C4；m1，m2，m3，m4)= 4；l=4，5，68l+1-12；l≥7ì?í????

證明 當l=4時，顯然χgvt(C4；1，1，1，1)≥4．因為3種顏色只能區別7個點，而圖2(a)給出了C4；1，1，1，1的4-GVDTC，因此χgvt(C4；1，1，1，1)=4．

當l=5時，顯然χgvt(C4；1，1，1，2)≥4．因為3種顏色只能區別7個點，而圖2(b)給出了C4；1，1，1，2的4-GVDTC，因此χgvt(C4；1，1，1，2)=4．

當l=6時，只需考慮C4；1，1，1，3、C4；1，1，2，2、C4；1，2，1，2即可．顯然對這3個圖，χgvt≥4，而圖2(c)、(d)、(e)分別給出了3個圖的4-GVDTC，故χgvt(C4；1，1，1，3)=χgvt(C4；1，1，2，2)=χgvt(C4；1，2，1，2)=4．

以下假設l≥7．

k=8l+1-12

(a) C4;1,1,1,1

(b) C4;1,1,1,2

(c) C4;1,1,1,3

(d) C4;1,1,2,2

(e) C4;1,2,1,2

讓C4；m1，m2，m3，m4的懸掛點ui，j沿襲在g下G′中對應的懸掛點ui，j的顏色，j=1，2，…，mi，i=1，2，3，4；讓C4；m1，m2，m3，m4的懸掛邊uiui，j沿襲在g下G′中對應的懸掛邊wui，j的顏色，j=1，2，…，mi，i=1，2，3，4．則在此基礎上以下只需考慮u1、u1u2、u2、u2u3、u3、u3u4、u4、u1u4的染色即可．

令Aui表示與ui關聯的懸掛邊的顏色構成的集合(非多重集)，i=1，2，3，4．以下分5種情況討論：

在這種情況下，可按圖3(a)、(b)、(c)、(d)、 (e) 所給出的方式分5種情形對圈上的點、邊進行染色．比如：在情形(a)中，邊u1u2、u2u3、u3u4、u1u4分別用3、4、4、1染色；點u1、u2、u3、u4分別用2、2、3、2染色．這時，Cf(u1)={1，2，3}，Cf(u2)={1，2，3，4}，Cf(u3)={1，3，4}，Cf(u4)={1，2，4}，其他頂點即懸掛點的色集合為1-子集或2-子集．因此所得的染色是k-GVDTC．在其他情形下，都可類似得到最終染色是k-GVDTC，且不再贅述．

(a)

(b)

(c)

(d)

(e)

圖3 情況(1)的示意圖

Fig.3 The schematic graph of case (1)

情形(a)記為情形(1，1，1，1)，情形(b)記為情形(1，1，1，2)，其他類似．除上述5種情形外，還有情形(1，2，2，2)等價于情形(b)；情形(1，2，2，3)與(1，2，3，3)均等價于情形(d)．因此，出現的這些情形將不再畫圖表示．

注記 圖3均為示意圖，在圖中只標出了與u1、u2、u3、u4關聯的懸掛邊顏色的種類，而與u1、u2、u3、u4關聯的懸掛邊的條數不僅僅只有圖中出現的條數．后面再出現時，不再作注解．

在這種情況下，可按圖4所給出的9種方式進行染色．

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

圖4 情況(2)的示意圖

Fig.4 The schematic graph of case (2)

情形(a)記為情形(1，1，1，12)，情形(b)記為情形(1，1，1，23)，其他類似．除上述9種情形外，還有情形(12，2，2，2)等價于情形(a)；情形(12，3，3，3)等價于情形(b)；情形(1，1，23，3)、(1，12，3，3)和(1，1，23，3)等價于情形(c)；情形(1，2，2，23)、(1，1，23，4)、(1，23，4，4)、(12，3，3，4)和(12，3，4，4)等價于情形(d)；情形(1，12，2，2)等價于情形(g)；情形(1，2，2，23)、(1，23，3，3)和(12，2，2，3)等價于情形(i)；情形(1，2，23，4)、(1，2，34，4)、(1，12，3，4)、(1，23，3，4)和(12，2，3，4)等價于情形(e)；情形(1，2，34，5)、(1，23，4，5)和(12，3，4，5)等價于情形(f)；情形(1，2，23，3)等價于情形(h)．因此，出現的這些情形將不再畫圖表示．

由懸掛邊染色規律得，Au3≠Au4，則Au4Au3≠?且Au3Au4≠?．設a，b∈Au3且a

由懸掛邊染色規律得，Au2≠Au4，則Au4Au2≠?且Au2Au4≠?．設a，b∈Au2且a

這時由懸掛邊染色規律得，Au2、Au3、Au4互不相同．設Au1={c0}，a，b∈Au4，且a

下面用c0染u1u4；用k-1染u1；用k分別去染u1u2、u2、u2u3、u3和u3u4；用{1，2，…，k}{c0，a，b}中某種顏色去染u4．在上述染色下，c0?Cf(u3)，而c0∈Cf(u1)∩Cf(u4)，故Cf(u3)≠Cf(ui)，i=1，4；Au2≠Au3，k?Au2∪Au3，故Cf(u2)≠Cf(u3)；|Cf(u1)|=3，|Cf(u4)|≥4，故Cf(u1)≠Cf(u4)；k-1∈Cf(u1)Cf(u2)，故Cf(u1)≠Cf(u2)；a∈Cf(u4)Cf(u2)，故Cf(u2)≠Cf(u4)．因此，所得的染色是C4；m1，m2，m3，m4的k-GVDTC．

這時由懸掛邊染色規律得，Au1、Au3、Au4互不相同．設Au2={c0}，a，b∈Au1，且a

這時由懸掛邊染色規律得，Au1、Au2、Au4互不相同．設Au3={c0}，d0∈Au1，a，b∈Au4，且a

下面用k-1染u3；用k分別去染u1、u1u2、u2、u2u3和u3u4；用d0染u1u4；用{1，2，…，k}{a，b，d0}中某種顏色去染u4．可以看出，上述染色是C4；m1，m2，m3，m4的k-GVDTC．

這時由懸掛邊染色規律得，Au1、Au2、Au3互不相同．設Au4={c0}，d0∈Au1，a，b∈Au3，且a

下面用a染u4；用k分別去染u1、u1u2、u2和u2u3；用d0染u3u4與u1u4；用{1，2，…，k}{a，b，d0}中某種顏色去染u3．可以看出，上述染色是C4；m1，m2，m3，m4的k-GVDTC．

由懸掛邊染色規律得，Au1、Au2、Au3、Au4互不相同．設a，b∈Au1且a

在上述染色下，a∈Cf(u1)∩Cf(u4)，而a?Cf(u2)∩Cf(u3)，|Cf(ui)|≥3，i=1，2，3，4，故Cf(ui)≠Cf(uj)，j=1，4，i=2,3；c?Cf(u1)，而c∈Cf(u4)，故Cf(u1)≠Cf(u4)；Au2≠Au3，k?Au2∪Au3，故Cf(u2)≠Cf(u3)．因此，所得的染色是C4；m1，m2，m3，m4的k-GVDTC．

綜上即得C4；m1，m2，m3，m4的k-GVDTCf．

3 結 語

在本文定理1中，通過探討一類含有4-圈的單圈圖的一般點可區別全染色，證明了它具有一般點可區別全染色，并得到了它的一般點可區別全色數．另外，一類含有4-圈的單圈圖是通過在4-圈的基礎上加懸掛點得到的，那么這種方法是不是可以繼續延續下去，進而得到一類含有n-圈的單圈圖(n≥5)的一般點可區別全色數?這就是今后需要繼續研究的課題．

[1] HARARY F, PLANTHOLT M. The point-distinguishing chromatic index [M] // HARARY F, MAYBEE J S, eds. Graphs and Application. New York: Wiley Interscience, 1985:147-162.

[5] CHEN Xiang′en, GAO Yuping, YAO Bing. Vertex-distinguishing IE-total colorings of complete bipartite graphsKm,n(m

[6] LIU Chanjuan, ZHU Enqiang. General vertex-distinguishing total colorings of graphs [J]. Journal of Applied Mathematics, 2014, 2014:849748.

General vertex-distinguishing total colorings of a family of unicyclic graphs includingC4

CHEN Xiang′en*1， LI Ting1， WANG Zhiwen2

( 1.College of Mathematics and Statistics, Northwest Normal University, Lanzhou 730070, China；2.School of Mathematics and Computer Sciences, Ningxia University, Yinchuan 750021, China )

LetGbe a simple graph. For a general total coloringfofG, ifC(u)≠C(v) for any two different verticesuandvofG, thenfis called a general vertex-distinguishing total coloring ofG(or GVDTC ofGfor short). The minimum number of colors required in a GVDTC is the general vertex-distinguishing total chromatic number. The general vertex-distinguishing total colorings of a family of unicyclic graphs includingC4are discussed by making the coloring of its pendent edges in an ascending order. It is determined that it has a general vertex-distinguishing total coloring ofGand its general vertex-distinguishing total chromatic number is got.

unicyclic graphs; general total coloring; general vertex-distinguishing total coloring; general vertex-distinguishing total chromatic number

1000-8608(2017)03-0316-05

2016-06-15；

2017-02-23．

國家自然科學基金資助項目(61163037，61163054，11261046)；寧夏回族自治區百人計劃資助項目.

陳祥恩*(1965-)，男，教授，E-mail:chenxe@nwnu.edu.cn；李 婷(1993-)，女，碩士生，E-mail:LTKR2016@126.com.

O157.5

A

10.7511/dllgxb201703015