 The Equitable Total Chromatic Number of SomeJoin graphsMA GangCollege of Mathematics and Computer ScienceNorthwest University for NationalitiesLanzhou, Gansu, China 730030Email: jsmg@xbmu.edu.cnTelephone:13909408935MA MingCollege of Mathematics and Computer ScienceNorthwest University for NationalitiesLanzhou, Gansu, China 730030Email: jsmm@xbmu.edu.cnTelephone:13669389252Abstract—A proper total-coloring of graph Gis said to beequitable if the number of elements (vertices and edges) in anytwo color classes differ by at most one, which the requiredminimum number of colors is called the equitable total chromaticnumber.In this paper,we prove some theorems on equitabletotal coloringand derive the equitabletotal chromatic numbersof Pm∨Sn,Pm∨Fnand Pm∨Wn.Keywords-join graph; equitable total coloring; equitabletotal chromatic numbersI. INTRODUCTIONThe coloring problem is one of the most important problemsin the graph theory. As an extension of proper vertex coloring,edge coloring and total coloring[1−5], the concept and someconjectures on the equitable total coloring[6−8] is developed.It is averydifﬁcultproblem to obtainthe equitable totalchromatic number, which meaningful results are rare.The adjacent vertex distinguishing-equitable total chromaticnumbers ofsomedoublegraphsare researchinreferences. Zhang et al.(2008) introduced the vertex distinguishingequitable edge coloring in references , and the vertexdistinguishing equitableedge chromaticnumbers ofthe join-graphs between path and path, path and cycle, cycle and cyclewith equivalent order are obtained in references .In this paper, we study the equitable total coloring of somejoin graphsand getsome results.Some termsand marksaren’tdescribed in this paper, please refer them to [1-3].II. DEFINITION AND LEMMADeﬁnition 2.1 Forasimple graphG(V,E), letfbeaproper k-edge coloring of G, and||Ei|−|Ej||≤1,i,j=1,2,··· ,k.The partition {Ei|1≤i≤k}is calleda k-equitable edgecoloring (k-PEEC of Gin brief), andχe(G)=min{k|k−PEEC of G}is calledthe equitable edgechromatic number ofG, where∀e∈Ei,f(e)=i,i =1,2,··· ,k.Deﬁnition 2.2[6−8] For a simple graph G(V,E), let fbea proper k-total coloring of G, and||Ti|−|Tj||≤1,i,j=1,2,··· ,k.The partition {Ti}={Vi∪Ei|1≤i≤k}is called a k-equitable total coloring (k-ETC of Gin brief), andχet(G)=min{k|k−ETC of G}is called the equitable total chromatic number of G,where∀x∈Ti=Vi∪Ei,f(x)=i,i =1,2,··· ,k.Conjecture2.1[6−8] For any simple graph G(V,E),χet(G)≤Δ(G)+2 and χet(G)=χt(G),where χt(G)is the total chromatic number of G.Deﬁnition 2.3 For graph Gand H(V(G)∩V(H)=φ, E(G)∩E(H)=φ), a new graph,denotedby G∨H,iscalled the join of Gand HifV(G∨H)=V(G)∪V(H),E(G∨H)=E(G)∪E(H)∪{uv|u∈V(G),v ∈V(H)}.Lemma 2.1[6−8] For any simple graph G(V,E),χet(G)≥Δ(G)+1.Lemma 2.2 For any simple graph G(V,E),χe(G)≥Δ(G).Foranysimple graph Gand H,χe(G)=χ(G), andifH⊆G,then χ(H)≤χ(G)[1,2], whereχ(G)is theproperedge chromaticnumberofG. SoLemma2.3and Lemma2.4are obtained.Lemma 2.3For any simple graphGand H,ifHis asubgraph of G, thenχe(H)≤χe(G).Lemma 2.4For complete graph Kpwith order p,χe(Kp)=p,p ≡1(mod 2),p−1,p≡0(mod 2).Lemma 2.5[2,5] Let Gbe a simple graph, if G[VΔ]doesnot contain cycle, thenχe(G)=Δ(G).Where V(G[VΔ]) = VΔ={v|d(v)=Δ(G),v ∈V(G)},E(G[VΔ]) = {uv|u, v∈VΔ,uv∈E(G)}.Open Journal of Applied Sciences Supplement：2012 world Congress on Engineering and Technology96 Copyright © 2012 SciRes. Lemma 2.6[6−8] For complete graph Kpwith order p,χet(Kp)=p,p ≡1(mod 2),p+1,p≡0(mod 2).Lemma 2.7Suppose Pmis aPath withorder m,Sn,Fnand WnareStar,Fanand Wheelwithorder n+1,respectively.ThenΔ(Pm∨Sn)=Δ(Pm∨Fn)=Δ(Pm∨Wn)=m+n.III. MAIN RESULTSForsomesimple graphs,we obtain Theorem3.1and The-orem 3.2 as following.Theorem 3.1Let Gbea simple graph, ifΔ(G)=|V(G)|−1and Gonly has a vertex with maximum degree, thenχet(G)=Δ(G)+1.Proof By Lemma2.1, we only prove that Ghas an fof(Δ(G)+1)-ETC.Suppose w∈ V(G),G∗=G∨{w},thenG∗[VΔ]=P2,soχe(G∗)=Δ(G∗)=Δ(G)+1byLemma2.5.Let f∗be a (Δ(G)+1)-PEEC of G,∀u∈V(G),f(u)=f∗(wu);∀uv ∈E(G),f(uv)=f∗(uv).Obviously,fisa(Δ(G)+1)-ETC ofG, sotheTheorem 3.1is true.Theorem 3.2Let Gbea simple graph, if Δ(G)=|V(G)|−1and |V(G)|≡ 1(mod 2), thenχet(G)=Δ(G)+1.ProofBy Lemma 2.1, we only prove that Ghas an fof n-ETC, where n=|V(G)|.Suppose w∈ V(G),G∗=G∨{w},obviouslyΔ(G∗)=n,G∗⊆Kn+1 and (n+1)≡0(mod2),so χe(G∗)=nby Lemma 2.2, Lemma 2.3 and Lemma 2.4.Let f∗be an n-PEEC of G,∀u∈V(G),f(u)=f∗(wu);∀uv ∈E(G),f(uv)=f∗(uv).Obviously,fis an n-ETC of G, so the Theorem 3.2 is true.In the following discussion, letPm=u1u2···um;V(Sn)={vi|i=0,1,2,··· ,n},E(Sn)={v0vi|i=1,2,··· ,n};V(Fn)={vi|i=0,1,2,··· ,n},E(Fn)={v0vi|i=1,2,··· ,n}∪{vivi+1 |i=1,2,··· ,n−1};V(Wn)={vi|i=0,1,2,··· ,n},E(Wn)={v0vi|i=1,2,··· ,n}∪{vivi+1 |i=1,2,··· ,n−1}∪{vnv1}.Theorem3.3When m≥2, thenχet(Pm∨Sn)=5,m=2,n=1,m+n+1,otherwise.ProofThere are seven cases to be considered.Case 1When m=2and n=1, obviously P2∨S1=K4.By Lemma 2.6, it’s clear that the result is true.Case 2Whenm=3,n=1or m=n=2,χet(P3∨S1)=χet(P2∨S2)=5by Lemma 2.7 and Theorem 3.2, so clearlythe result is true.Case 3When m=2and n=3,χet (P3∨S3)≥6by Lemma2.1 and Lemma2.7.Weonly need toprovethatP2∨S3has an fof 6-ETC. Deﬁne fbyf(v0v1)=f(v2u1)=f(u2)=1;f(v0v2)=f(v3u2)=f(u1)=2;f(v1u2)=f(v3u1)=f(v0)=3;f(v0u1)=f(v2u2)=f(v3)=4;f(v0u2)=f(v1u1)=f(v2)=5;f(v0v3)=f(u1u2)=f(v1)=6.Obviously,thefis a6-ETC of P2∨S3, so theresult is true.Case 4When m=2and n≥4,χet(P2∨Sn)≥n+3byLemma 2.1 and Lemma 2.7. We only need to prove that P2∨Snhas an fof (n+3)-ETC. Let matching M={v0v1,u1u2}.Suppose w/∈V(P2∨Sn), denote G∗byV(G∗)=V(P2∨Sn)∪{w},E(G∗)=E(P2∨Sn\M)∪{wu1,wu2}∪{wvi|i=0,1,··· ,n−2}.Hence G∗[VΔ]=u1v0u2isaPath withorder3, so χe(G∗)=Δ(G∗)=n+2 by Lemma 2.5.Let f1be an (n+2)-PEEC of G∗, let f2be a mapping ofP2∨Snbased on f1, that is,f2(ui)=f1(wui),i=1,2;f2(vi)=f1(wvi),i=0,1,··· ,n−2.Deﬁne mapping f3byf3(v0v1)=f3(u1u2)=f3(un−1)=f3(un)=n+3.Put f=f1∪f2∪f3. So, for P2∨Sn,we∀i∈{1,2,··· ,n+3},|Ti|=3or 4.Obviously, fis an (n+3)-ETCof P2∨Sn, hence the resultis true.Case 5Whenm≥4andn=1,χet(Pm∨S1)≥m+2byLemma 2.1 and Lemma 2.7. We only need to prove that Pm∨S1hasanfof (m+2)-ETC. Let matchingM={v0v1,u2u3}.Suppose w/∈V(Pm∨S1), denote G∗byV(G∗)=V(Pm∨S1)∪{w},E(G∗)=E(Pm∨S1\M)∪{wv0,wv1}∪{wui|i=2,3,··· ,m}.Hence G∗[VΔ]=v0wv1is a Pathwith order 3,so χe(G∗)=Δ(G∗)=m+1 by Lemma 2.5.Let f1be an (m+1)-PEEC ofG∗,let f2beamapping ofPm∨S1based on f1, that is,f2(vi)=f1(wvi),i=0,1;f2(ui)=f1(wui),i=2,3,··· ,m.Deﬁne mapping f3byf3(v0v1)=f3(u2u3)=f3(u1)=m+2.Put f=f1∪f2∪f3. So, for Pm∨S1,wehave∀i∈{1,2,··· ,m+2},|Ti|=3,m=4,3or4,m≥5.Obviously, fis an (m+2)-ETC of Pm∨S1, hencetheresultis true.Case 6When m=3and n≥2,χet(P3∨Sn)≥n+4byLemma 2.1 and Lemma 2.7. We only need to prove that P3∨Copyright © 2012 SciRes.97 Snhasanfof(n+4)-ETC. Letmatching M={v0v1,v2u2}.Suppose w/∈V(P3∨Sn), denote G∗byV(G∗)=V(P3∨Sn)∪{w},E(G∗)=E(P3∨Sn\M)∪{wu2}∪{wvi|i=0,1,··· ,n}.Hence G∗[VΔ]=v0u2is a Path with order 2,so χe(G∗)=Δ(G∗)=n+3 by Lemma 2.5.Let f1be an (n+3)-PEEC of G∗, let f2be a mapping ofP3∨Snbased on f1, that is,f2(u2)=f1(wu2);f2(vi)=f1(wvi),i=0,1,··· ,n.Deﬁne mapping f3byf3(v0v1)=f3(v2u2)=f3(u1)=f3(u3)=n+4.Put f=f1∪f2∪f3. So, for P3∨Sn,wehave∀i∈{1,2,··· ,n+4},|Ti|=⎧⎨⎩3or4,2≤n≤6,4,n=7,4or5,n≥8.Obviously, fis an (n+4)-ETCof P3∨Sn, hence the resultis true.Case 7When m≥4and n≥2,Pm∨Snonly has avertexv0with maximumdegreeand d(v0)=m+n=|V(Pm∨Sn)|−1, so clearly the result is true by Theorem 3.1.From what stated above, the proof is completed.Theorem3.4When m≥2and n≥2, thenχet(Pm∨Fn)=7,m=2,n=3orm=3,n=2,m+n+1,otherwise.ProofSincePm∨Fn∼=Pn∨Fm, soweonly prove thatthe result is true when m≥n≥2. There are six cases to beconsidered.Case 1When m=n=2, obviously P2∨F2=K5.ByLemma 2.6, it’s clear that the result is true.Case 2When m=3and n=2,χet(P3∨F2)≥6byLemma 2.1andLemma2.7, obviously P3∨F2=K6−u1u3.Suppose χet(K6−u1u3)=6,onlythe color contains atmost4 elements which colored u1and u3, each color of the leftcontains 3elements,so6colorscolored atmost19elements,but |V(K6−u1u3)|+|E(K6−u1u3)|=20.Hence,6-ETC isimpossible.Moreover, 7-ETCof P3∨F2is getatable,denote fbyf(uivj)=i+j,i =1,2,3,j=0,1,2;f(u1u2)=f(v1)=5; f(u3)=2; f(v0)=4;f(u2u3)=f(v0v1)=f(v2)=6;f(v0v2)=f(u1)=7; f(v1v2)=f(u2)=1.Obviously, fis a 7-ETC of P3∨F2, hencethe result is true.Case 3Whenm≥4and n=2,χet(Pm∨F2)≥m+3by Lemma 2.1 and Lemma 2.7. We only prove that Pm∨F2has anfof(m+3)-ETC.Let matching M={v0u2,v1v2}.Suppose w/∈V(Pm∨F2), denote G∗byV(G∗)=V(Pm∨F2)∪{w},E(G∗)=E(Pm∨F2\M)∪{wv0,wv1,wv2,wu2}∪{wui|i=4,5,··· ,m}.Hence G∗[VΔ]=v1v0v2is a Path with order 3,so χe(G∗)=Δ(G∗)=m+2 by Lemma 2.5.Let f1be an (m+2)-PEEC ofG∗,let f2beamapping ofPm∨F2based on f1, that is,f2(vi)=f1(wvi),i=0,1,2; f2(u2)=f1(wu2);f2(ui)=f1(wui),i=4,5,··· ,m.Deﬁne mapping f3byf3(v1v2)=f3(v0u2)=f3(u1)=f3(u3)=m+3.Put f=f1∪f2∪f3. So, for Pm∨F2,wehave∀i∈{1,2,··· ,m+3},|Ti|=⎧⎨⎩3or 4,m=4,5,6,4,m=7,4or 5,m≥8.Obviously, fis an (m+3)-ETC of Pm∨F2, hence the resultis true.Case 4When m=n=3,χet(P3∨F3)=7 by Lemma2.7 and Theorem 3.2, so clearly the result is true.Case 5When m>n=3,χet(Pm∨F3)≥m+4 byLemma 2.1 and Lemma 2.7. We only prove that Pm∨F3hasan fof(m+4)-ETC. LetmatchingM={v1u2,v0v2,v3u3}.Suppose w/∈V(Pm∨F3), denote G∗byV(G∗)=V(Pm∨F3)∪{w},E(G∗)=E(Pm∨F3\M)∪{wu |u∈V(Pm∨F3),and u=u1,um}.Hence G∗[VΔ]=v0v2isa Pathwith order2,so χe(G∗)=Δ(G∗)=m+3 by Lemma 2.5.Let f1be an (m+3)-PEEC ofG∗,let f2beamapping ofPm∨F3based on f1, that is,f2(u)=f1(wu),u∈V(Pm∨F3),and u=u1,um.Deﬁne mapping f3byf3(v1u2)=f3(v0v2)=f3(v3u3)=f3(u1)=f3(um)=m+4.Put f=f1∪f2∪f3. So, for Pm∨F3,wehave∀i∈{1,2,··· ,m+4},|Ti|=⎧⎪⎪⎨⎪⎪⎩4,m=4,4or 5,5≤m≤11,5,m=12,5or 6,m≥13.Obviously, fis an (m+4)-ETC of Pm∨F3, hence the resultis true.Case 6When m≥n≥4,Pm∨Fnonly has a vertex v0with maximumdegree andd(v0)=m+n=|V(Pm∨Fn)|−1, so clearly the result is true by Theorem 3.1.From what stated above, the proof is completed.Theorem3.5When m≥2and n≥3, thenχet(Pm∨Wn)=7,m=2,n=3,m+n+1,otherwise.ProofThere are six cases to be considered.Case 1Whenm=2and n=3,obviously P2∨W3=K6.By Lemma 2.6, it’s clear that the result is true.Case 2When m=2,n =4or m=n=3,χet(P2∨W4)=χet(P3∨W3)=7by Lemma 2.7 and Theorem3.2,so clearly the result is true.Case 3When m=2and n≥5,χet(P2∨Wn)≥n+3by Lemma 2.1and Lemma 2.7. We only prove thatP2∨Wnhas an fof (n+3)-ETC. Deﬁne fbyf(viuj)=i+j,i =0,1,··· ,n,j =1,2;98 Copyright © 2012 SciRes. f(v0vi)=i+3,i=1,2,··· ,n;f(v0)=3;f(u1u2)=f(v1)=f(v3)=n+3;f(v1v2)=n+1;f(v2v3)=f(u1)=n+2; f(v2)=2;f(vivi+1)=i−2,i=3,4,··· ,n−1;f(vmv1)=f(u2)=1;f(vi)=i,i =4,5,··· ,n.We have∀i∈{1,2,··· ,m+3},|Ti|=⎧⎨⎩3or 4,n=5,4,n=6,4or 5,n≥7.Obviously, the fisan(n+3)-ETC of P2∨Wn, hencetheresult is true.Case 4When m=3and n≥4,χet(P3∨Wn)≥n+4byLemma 2.1 and Lemma 2.7. We only prove that P3∨Wnhasan fof (n+4)-ETC.Let matchingM={v0u2,v1v2,v3v4}.Suppose w/∈V(P3∨Wn), denote G∗byV(G∗)=V(P3∨Wn)∪{w},E(G∗)=E(P3∨Wn\M)∪{wu2}∪{wvi|i=0,1,··· ,n}.Hence theedge set ofG∗[VΔ]isempty, soχe(G∗)=Δ(G∗)=n+3 by Lemma 2.5.Let f1be an (n+3)-PEEC of G∗, let f2be a mapping ofP3∨Wnbased on f1, that is,f2(u2)=f1(wu2);f2(vi)=f1(wvi),i=0,1,··· ,n.Deﬁne mapping f3byf3(v0u2)=f3(v1v2)=f3(v3v4)=f3(u1)=f3(u3)=n+4.Put f=f1∪f2∪f3. So, for P3∨Wn,wehave∀i∈{1,2,··· ,n+4},|Ti|=⎧⎨⎩4or 5,4≤n≤10,5,n=11,5or 6,n≥12.Obviously, fisan(n+4)-ETCofP3∨Wn,hence theresultis true.Case 5When m≥4andn=3,χet(Pm∨W3)≥m+4 byLemma 2.1and Lemma2.7. We onlyprovethat Pm∨W3has an fof (m+4)-ETC.Let edge setM={v0v1,v2v3,u2u3;v0v3,v1v2,u1u2}. Suppose w/∈V(Pm∨W3), denote G∗byV(G∗)=V(Pm∨W3)∪{w},E(G∗)=E(Pm∨W3\M)∪{wvi|i=0,1,2,3}∪{wu2}∪{wui|i=6,7,··· ,m, m≥6}.Hence theedgeset of G∗[VΔ]is{v0v2,v1v3},χe(G∗)=Δ(G∗)=m+2 by Lemma 2.5.Let f1be an (m+2)-PEEC ofG∗,let f2beamapping ofPm∨W3based on f1, that is,f2(u2)=f1(wu2);f2(vi)=f1(wvi),i=0,1,2,3;f2(ui)=f1(wui),i=6,7,··· ,m, (m≥6).Deﬁne mapping f3byf3(v0v1)=f3(v2v3)=f3(u2u3)=f3(u1)=f3(u4)=m+3;f3(v0v3)=f3(v1v2)=f3(u1u2)=f3(u3)=f3(u5)=m+4,(only if m≥5,has it vertex u5).Put f=f1∪f2∪f3. So, for Pm∨W3,wehave∀i∈{1,2,··· ,m+4},|Ti|=⎧⎨⎩4or 5,4≤m≤10,5,m=11,5or 6,m≥12.Obviously, fis an(m+4)-ETC ofPm∨W3,hencethe resultis true.Case 6Whenm≥4andn≥4,Pm∨Wnonly hasa vertex v0withmaximum degreeand d(v0)=m+n=|V(Pm∨Wn)|−1, so clearly the result is true by Theorem3.1.From what stated above, the proof is completed.ACKNOWLEDGMENTThis paper supported by the National Natural ScienceFoundation of China(61163037),the Fundamental ResearchFunds for the Central Universities of Northwest Universityfor Nationalities(ZYZ2011082,ZYZ2011077).Corresponding author:MA Ming,CollegeofMath-ematics and Computer Science, Northwest University forNationalities, Lanzhou, Gansu, China 730030, Email:jsmm@xbmu.edu.cnREFERENCESH. P. Yap,Total Colorings of Graphs, Berlin: Lecture Notes in Mathe-matics, 1623, Springer, 1996.J.A.Bondy,U. S. R.Murty, GraphTheorywith Applications,New York:The Macmillan Press Ltd, 1976.Tian Feng, MAZhong-fan,Graph Theoryand NetworkFlow Theory,Beijin: Science Press, 1987.Zhang Zhong-fu, Wang Jian-fang, The Progress ofTotal-ColouringofGraphs, Advances in Mathematics, 1992,21(4):390-397.Zhang Zhong-fu,Zhang Jian-xun, OnSome SufﬁcientConditions of FirstKind Graph, Journal of Mathematics, 1985,5(2):161-165.Ma Gang,Zhang Zhong-fu, Onthe Equitable Total Coloring of Mul-tiple Join-graph,JournalofMathematicalResearchandExposition,2007,27(2):351-354. Wang Wei-fan, Equitable Total Coloringof Graphs with MaximumDegree 3, Graphs and Combin, 2002,18:677-685.Ma Gang, Zhang Zhong-fu, Qiang Hui-ying, Onequitable total chro-matic numberof CmFn,Journalof Lanzhou JiaotongUniversity,2005,24(4):147-149.Ma Gang, Zhang Zhong-fu, on Adjacent Vertex-distinguishing-equitableTotalColoring of Double Graphs, J. of Jilin University (ScienceEdition),2009, 47(6): 1160-1164.Zhang Zhong-fu,Li Mu-chun, Yao Bin, etal, On theVertex Distin-guishing Equitable Edge-coloring of Graphs, ARS Combinatoria, 2008,86: 193-200.Zhang Zhong-fu, Li Jing-wen, Zhao Chuan-cheng, et al, On the Vertex-distinguishing-equitable Edge Chromatic of someJoin-graphs, ActaMathematica Sinica, Chinese Series, 2007, 50(1): 197-204.Copyright © 2012 SciRes.99