On Chromatic Number and Adjacent Vertex-dis⁃tinguishing E-total Chromatic Number of Graphs

ZHENG Yirong，CEHN Meirun，ZHAI Shaohui

（1.School of Applied Mathematics，Xiamen University of Technology，Xiamen361024，China；2.Center for Discrete Mathematics，Fuzhou University，Fuzhou350116，China）

On Chromatic Number and Adjacent Vertex-dis⁃tinguishing E-total Chromatic Number of Graphs

ZHENG Yirong1，2，CEHN Meirun1，ZHAI Shaohui1

（1.School of Applied Mathematics，Xiamen University of Technology，Xiamen361024，China；2.Center for Discrete Mathematics，Fuzhou University，Fuzhou350116，China）

The chromatic number of a graphG,denoted byχ（G）,is the minimum number k for whichGhas a properk-vertex coloring.The adjacent vertex-distinguishingE-total chromatic number ofG,denoted byis the minimum numberkfor whichGhas an adjacent vertex-distinguishingE-total coloring.These two colorings seem to be different,but we proved that

chromatic number；adjacent vertex-distinguishingE-total chromatic number

CLC mumber：O 157.5Document code：AArticle ID：1674-4942(2015)02-0131-03

1 Introduction

Coloring is an important topic in the study of graph theory.They arise naturally in many practical situations where it is required to partition a set of objects into groups in such a way that the members of each group are mutually compatible according to some criterion.There are many different kinds of coloring，such as ver⁃tex coloring，edge coloring，total coloring，adjacent-ver⁃tex-distinguishing total coloring and so on（see[2-4]）.The fundamental problem of coloring is to determine the number of various kinds of colorings.

First，we introduce some notations and definitions.LetGbe a simple graph，we useV（G），E（G）and Δ（G）to denote the vertex set，edge set and maximum degree ofGrespectively.The order ofGis the number of its vertices.Kn，Pn，Cn，Fn，andWndenote complete graph，path，cycle，fan，and wheel of ordernrespectively.LetViandVjbe the disjoint subsets ofV（G），we denote by[Vi，Vj]the set of edges with one end inViand the other end inVj.

Letkbe a positive integer andSbe a set ofkcol⁃ors.Usually，the set S of colors is taken to be{0，1，…，k-1}.A properk-vertex coloring is an assignment ofkcolors to the vertices ofGsuch that no two adjacent ver⁃tices are assigned the same color.Alternatively，a prop⁃er k-vertex coloring may be viewed as a partition（V0，V1，…，Vk-1）ofV（G），whereVidenotes the set（possibly empty）of vertices assigned colori.The chromatic num⁃ber ofG，denoted byχ()G,is the minimum numberkfor whichGhas a proper k-vertex coloring.The con⁃cept of adjacent-vertex-distinguishingE-total color-ing（k-AVDETC for short）of graph was proposed in[5]by Zhang et al.Ak-AVDETC is a mapping f fromV（G）∪E（G）to{0，1，…，k-1}such thatf（u），f（v），f（uv）are different andC（u）≠C（v）for anyuv∈E(G),whereC(u)={f(u)}∪{f(uv)|uv∈E(G)}.The mini⁃mum numberkfor whichGhas ak-AVDETC is called the adjacent vertex-distinguishingE-total chromatic number ofGand denoted byIn[5]-[9]Zhang et al.determinedfor many basic families of graphs including the Cartesian product graphsPm×Pn，Pm×Cn，Cm×Cn，the join graphsPm∨Fn，Pm∨Wn，Pm∨SnandPm∨Kn，the multiple join graphs of some graphs by giving a spe⁃cialk-AVDETC ofG.

2 Main Results

Firstly，we give two propositions ofk-AVDETC ofG.Let f be ak-AVDETC ofG，then for any edge uv ofG，f（u），f（v），f（uv）must be different，so we could easily get the following result.

Proposition 1.For any simple graphG，ifE（G）≠∅，thenIt is obvious that anyk-AVDETC ofGis a properk-vertex coloring ofGand that we can get a（k+1）-AV⁃DETC ofGfrom any properk-vertex coloring ofGby coloring every edge inGwith same color which is not used before.So,it follows that

Proposition 2.[5]For any simple graphG，

Thus，for any simple graphG，ifχ（G）=2（i.eGis a bipartite graph），then3 andare both possible(since it is not diffi⁃cult to check that

but whenχ（G）≥4，we will prove thatwhich is the main result of this paper.

Theorem 1 For any simple graphG，ifχ（G）=k（k≥4），then

Before giving the proof of Theorem1，we first give the definition of an optimal proper k-vertex coloring ofG，which is useful in the proof of our main result.

Definition 1 An optimal properk-vertex coloring ofGis a properk-vertex coloring with the partition（V0，V1，…，Vk-1）ofV（G）such that for any vertexvi∈Vi（i=0，1，…，k-2）and anyj（i+1≤j≤k-1）there exist at least one vertexvj∈Vjwhich is adjacent withvi.

Lemma 1 For any graphGwithχ（G）=k（k≥2），there exists an optimal properk-vertex coloring ofG.

ProofLet f be a properk-vertex coloring ofGwith the partition（V0，V1，…，Vk-1）ofV（G），if for vertex vi there does not exist vertexvj∈Vj(i＜j)such thatviandvjare adjacent，then we could recolorviwith colorj.Finally，an optimal properk-vertex coloring follows by repeating this progress.

Now，we give the proof of Theorem1.

ProofAccording to Proposition 2，we only need to prove thatGhas ak-AVDETC ifχ（G）=k.By Lemma 1，there always exists an an optimal proper k-vertex col⁃oringfofGwith the partition（V0，V1，…，Vk-1）ofV（G）satisfying thatf（v）=ifor any vertexv∈Vi（0≤i≤j≤k-1）.Now we distinguish the following two cases：

Case 1：k=4.For each edgeeofG，we definef（e）as follows：

Case 2：k≥5 For each edgee∈E(G)，let （fe）as follows（shown in Fig.1）：

图1 图G的邻点可区别E-全染色Fig.1k-AVDETC ofG

It is not difficult to verity thatfis ak-AVDETC ofG.

3 Remarks

The Cartesian product of two graphsG1andG2is the graphG1×G2whose vertex set isV（G1）×V（G2）and whose edge set is the set of all pairs（u，v）（u′，v′）such that eitheru=u′andvv′∈E(G2)orv=v′anduu′∈E(G1).The（multiple）join graph ofG1，…，G（tt＞2）is the graphG1∨…∨Gtwhose vertex set isV（G1）∪…∪V（G）tand whose edge set is

In[5]-[9]，Zhang et al.determined the adjacent vertex-distinguishing E-total chromatic number for some class of graphs，such as Cartesian product of some graphs，multiple join graphs of some graphs by giving a specialk-AVDETC.The chromatic number of the Car⁃tesian productG1×G2and the multiple join graphG1∨…∨Gtcan be easy determined by the following relations.

Proposition 3.For two simple graphsG1andG2，χ（G1×G2）=max{χ（G1），χ（G2）}.

Proposition 4.For simple graphsG1，G2…，Gt，Now，with the main result of this paper and Propo⁃sitions 3 and 4，we can determineandquite easily without giving a special arrangement of colors.

[1]Bondy J A,Murty U S R.Graph Theory with Applications[M].New York:Elsevier Science Publishing Co,1976.

[2]Behzad M.Graphs and their chromatic numbers[D].East Lansing:Michigan State University:1965.

[3]Zhang Z F,Chen X E.On adjacent vertex-distinguishing total coloring of graphs[J].Science in China,Series A,2005,48:289-299.

[4]Zhang Z F,Qiu P X.Vertex-distinguishing total coloring of graphs[J].Ars Comninatoria,2008,87:33-45.

[5]Li M,Zhang Z F.Adjacent vertex-distinguishing E-total coloring on Product of some graphs[J].Mathematics in Practice and Theory,2009,39:215-219.

[6]Li M,Zhang Z.Adjacent vertex-distinguishing E-total col⁃oring on join graphs of Pm Gn[J].Journal of Northwest Normal University,2009,45:24-29.

[7]Li M,Hu C,Zhang Z F.Adjacent vertex-distinguishing E-total coloring on the multiple join Graph of Odd cycle,even cycle and wheel[J].Journal of Zhengzhou University:Natu⁃ral science,2009,41:1-6.

[8]Li M,Zhang Z F.Adjacent vertex-distinguishing E-total coloring on the multiple join Graph of some graphs[J].Jour⁃nal of Lanzhou Jiaotong University:Natural science,2009,28:149-152.

[9]Li M,Zhang Z F.Adjacent vertex-distinguishing E-total coloring on a class of the multiple join graphs[J].Pure and Applied Mathematics,2010,26:36-41.

责任编辑：刘 红

关于图的点色数和邻点可区别E-全色数

郑艺容1，2，陈美润1，翟绍辉1

（1.厦门理工学院应用数学学院，福建，厦门 361024；2.福州大学离散数学研究中心，福建，福州 350116）

图G的点色数χ（G）是指图G存在正常k-顶点着色的k的最小值，图G的邻点可区别E-全色数是指图G存在邻点可区别E-全染色的k的最小值.尽管图G的这两种染色看似不同，但我们证明：当χ（G）≥4时，

点色数；邻点可区别E-全色数

2015-03-01

国家青年自然科学基金项目（11301440）；福建省教育厅自然科学基金项目（JA13240，JB13155）；厦门理工学院科技项目（xkjj 201106）