Paper Menu >>
Journal Menu >>
The Equitable Total Chromatic Number of Some Join graphs MA Gang College of Mathematics and Computer Science Northwest University for Nationalities Lanzhou, Gansu, China 730030 Email: jsmg@xbmu.edu.cn Telephone:13909408935 MA Ming College of Mathematics and Computer Science Northwest University for Nationalities Lanzhou, Gansu, China 730030 Email: jsmm@xbmu.edu.cn Telephone:13669389252 Abstract—A proper total-coloring of graph Gis said to be equitable if the number of elements (vertices and edges) in any two color classes differ by at most one, which the required minimum number of colors is called the equitable total chromatic number.In this paper,we prove some theorems on equitable total coloringand derive the equitabletotal chromatic numbers of Pm∨Sn,Pm∨Fnand Pm∨Wn. Keywords-join graph; equitable total coloring; equitable total chromatic numbers I. INTRODUCTION The coloring problem is one of the most important problems in the graph theory. As an extension of proper vertex coloring, edge coloring and total coloring[1−5], the concept and some conjectures on the equitable total coloring[6−8] is developed. It is averydifficultproblem to obtainthe equitable total chromatic number, which meaningful results are rare. The adjacent vertex distinguishing-equitable total chromatic numbers ofsomedoublegraphsare researchinreferences [9]. Zhang et al.(2008) introduced the vertex distinguishing equitable edge coloring in references [10], and the vertex distinguishing equitableedge chromaticnumbers ofthe join- graphs between path and path, path and cycle, cycle and cycle with equivalent order are obtained in references [11]. In this paper, we study the equitable total coloring of some join graphsand getsome results.Some termsand marksaren’t described in this paper, please refer them to [1-3]. II. DEFINITION AND LEMMA Definition 2.1[2] Forasimple graphG(V,E), letfbea proper k-edge coloring of G, and ||Ei|−|Ej||≤1,i,j=1,2,··· ,k. The partition {Ei|1≤i≤k}is calleda k-equitable edge coloring (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. Definition 2.2[6−8] For a simple graph G(V,E), let fbe a 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. Definition 2.3[2] For graph Gand H(V(G)∩V(H)= φ, E(G)∩E(H)=φ), a new graph,denotedby G∨H,is called the join of Gand Hif V(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[2] For any simple graph G(V,E), χ e(G)≥Δ(G). Foranysimple graph Gand H,χ e(G)=χ(G)[6], andif H⊆G,then χ(H)≤χ(G)[1,2], whereχ(G)is theproper edge chromaticnumberofG. SoLemma2.3and Lemma2.4 are obtained. Lemma 2.3For any simple graphGand H,ifHis a subgraph 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Δ]does not 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 Technology 96 Cop y ri g ht © 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,Fn and WnareStar,Fanand Wheelwithorder n+1,respectively. Then Δ(Pm∨Sn)=Δ(Pm∨Fn)=Δ(Pm∨Wn)=m+n. III. MAIN RESULTS Forsomesimple 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},then G∗[VΔ]=P2,soχ e(G∗)=Δ(G∗)=Δ(G)+1byLemma 2.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.1 is 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, let Pm=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 clearly the result is true. Case 3When m=2and n=3,χet (P3∨S3)≥6 by Lemma2.1 and Lemma2.7.Weonly need toprovethat P2∨S3has an fof 6-ETC. Define fby f(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+3by Lemma 2.1 and Lemma 2.7. We only need to prove that P2∨ Snhas an fof (n+3)-ETC. Let matching M={v0v1,u 1u2}. Suppose w/∈V(P2∨Sn), denote G∗by V(G∗)=V(P2∨Sn)∪{w}, E(G∗)=E(P2∨Sn\M)∪{wu1,wu 2}∪{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 of P2∨Snbased on f1, that is, f2(ui)=f1(wui),i=1,2; f2(vi)=f1(wvi),i=0,1,··· ,n−2. Define mapping f3by f3(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 result is true. Case 5Whenm≥4andn=1,χet(Pm∨S1)≥m+2by Lemma 2.1 and Lemma 2.7. We only need to prove that Pm∨ S1hasanfof (m+2)-ETC. Let matchingM={v0v1,u 2u3}. Suppose w/∈V(Pm∨S1), denote G∗by V(G∗)=V(Pm∨S1)∪{w}, E(G∗)=E(Pm∨S1\M)∪{wv0,wv 1}∪{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 of Pm∨S1based on f1, that is, f2(vi)=f1(wvi),i=0,1; f2(ui)=f1(wui),i=2,3,··· ,m. Define mapping f3by f3(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, hencetheresult is true. Case 6When m=3and n≥2,χet(P3∨Sn)≥n+4by Lemma 2.1 and Lemma 2.7. We only need to prove that P3∨ Cop y ri g ht © 2012 SciRes.97 Snhasanfof(n+4)-ETC. Letmatching M={v0v1,v 2u2}. Suppose w/∈V(P3∨Sn), denote G∗by V(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 of P3∨Snbased on f1, that is, f2(u2)=f1(wu2); f2(vi)=f1(wvi),i=0,1,··· ,n. Define mapping f3by f3(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 result is true. Case 7When m≥4and n≥2,Pm∨Snonly has avertex v0with 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 that the result is true when m≥n≥2. There are six cases to be considered. Case 1When m=n=2, obviously P2∨F2=K5.By Lemma 2.6, it’s clear that the result is true. Case 2When m=3and n=2,χet(P3∨F2)≥6by Lemma 2.1andLemma2.7, obviously P3∨F2=K6−u1u3. Suppose χet(K6−u1u3)=6,onlythe color contains atmost 4 elements which colored u1and u3, each color of the left contains 3elements,so6colorscolored atmost19elements, but |V(K6−u1u3)|+|E(K6−u1u3)|=20.Hence,6- ETC isimpossible.Moreover, 7-ETCof P3∨F2is getatable, denote fby f(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+3 by Lemma 2.1 and Lemma 2.7. We only prove that Pm∨F2 has anfof(m+3)-ETC.Let matching M={v0u2,v 1v2}. Suppose w/∈V(Pm∨F2), denote G∗by V(G∗)=V(Pm∨F2)∪{w}, E(G∗)=E(Pm∨F2\M)∪{wv0,wv 1,wv 2,wu 2}∪ {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 of Pm∨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. Define mapping f3by f3(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 result is true. Case 4When m=n=3,χet(P3∨F3)=7 by Lemma 2.7 and Theorem 3.2, so clearly the result is true. Case 5When m>n=3,χet(Pm∨F3)≥m+4 by Lemma 2.1 and Lemma 2.7. We only prove that Pm∨F3has an fof(m+4)-ETC. LetmatchingM={v1u2,v 0v2,v 3u3}. Suppose w/∈V(Pm∨F3), denote G∗by V(G∗)=V(Pm∨F3)∪{w}, E(G∗)=E(Pm∨F3\M)∪{wu |u∈V(Pm∨ F3),and u=u1,u m}. 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 of Pm∨F3based on f1, that is, f2(u)=f1(wu),u∈V(Pm∨F3),and u=u1,u m. Define mapping f3by f3(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 result is true. Case 6When m≥n≥4,Pm∨Fnonly has a vertex v0 with 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+3 by Lemma 2.1and Lemma 2.7. We only prove thatP2∨Wn has an fof (n+3)-ETC. Define fby f(viuj)=i+j,i =0,1,··· ,n,j =1,2; 98 Cop y ri g ht © 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, hencethe result is true. Case 4When m=3and n≥4,χet(P3∨Wn)≥n+4by Lemma 2.1 and Lemma 2.7. We only prove that P3∨Wnhas an fof (n+4)-ETC.Let matchingM={v0u2,v 1v2,v 3v4}. Suppose w/∈V(P3∨Wn), denote G∗by V(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 of P3∨Wnbased on f1, that is, f2(u2)=f1(wu2);f2(vi)=f1(wvi),i=0,1,··· ,n. Define mapping f3by f3(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 theresult is true. Case 5When m≥4andn=3,χet(Pm∨W3)≥ m+4 byLemma 2.1and Lemma2.7. We onlyprove that Pm∨W3has an fof (m+4)-ETC.Let edge set M={v0v1,v 2v3,u 2u3;v0v3,v 1v2,u 1u2}. Suppose w/∈ V(Pm∨W3), denote G∗by V(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,v 1v3},χ e(G∗)= Δ(G∗)=m+2 by Lemma 2.5. Let f1be an (m+2)-PEEC ofG∗,let f2beamapping of Pm∨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). Define mapping f3by f3(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 result is true. Case 6Whenm≥4andn≥4,Pm∨Wnonly has a vertex v0withmaximum degreeand d(v0)=m+n=| V(Pm∨Wn)|−1, so clearly the result is true by Theorem 3.1. From what stated above, the proof is completed. ACKNOWLEDGMENT This paper supported by the National Natural Science Foundation of China(61163037),the Fundamental Research Funds for the Central Universities of Northwest University for Nationalities(ZYZ2011082,ZYZ2011077). Corresponding author:MA Ming,CollegeofMath- ematics and Computer Science, Northwest University for Nationalities, Lanzhou, Gansu, China 730030, Email: jsmm@xbmu.edu.cn REFERENCES [1]H. P. Yap,Total Colorings of Graphs, Berlin: Lecture Notes in Mathe- matics, 1623, Springer, 1996. [2]J.A.Bondy,U. S. R.Murty, GraphTheorywith Applications,New York: The Macmillan Press Ltd, 1976. [3]Tian Feng, MAZhong-fan,Graph Theoryand NetworkFlow Theory, Beijin: Science Press, 1987. [4]Zhang Zhong-fu, Wang Jian-fang, The Progress ofTotal-Colouringof Graphs, Advances in Mathematics, 1992,21(4):390-397. [5]Zhang Zhong-fu,Zhang Jian-xun, OnSome SufficientConditions of First Kind Graph, Journal of Mathematics, 1985,5(2):161-165. [6]Ma Gang,Zhang Zhong-fu, Onthe Equitable Total Coloring of Mul- tiple Join-graph,JournalofMathematicalResearchandExposition, 2007,27(2):351-354. [7] Wang Wei-fan, Equitable Total Coloringof Graphs with Maximum Degree 3, Graphs and Combin, 2002,18:677-685. [8]Ma Gang, Zhang Zhong-fu, Qiang Hui-ying, Onequitable total chro- matic numberof CmFn,Journalof Lanzhou JiaotongUniversity, 2005,24(4):147-149. [9]Ma Gang, Zhang Zhong-fu, on Adjacent Vertex-distinguishing-equitable TotalColoring of Double Graphs, J. of Jilin University (ScienceEdition), 2009, 47(6): 1160-1164. [10]Zhang Zhong-fu,Li Mu-chun, Yao Bin, etal, On theVertex Distin- guishing Equitable Edge-coloring of Graphs, ARS Combinatoria, 2008, 86: 193-200. [11]Zhang Zhong-fu, Li Jing-wen, Zhao Chuan-cheng, et al, On the Vertex- distinguishing-equitable Edge Chromatic of someJoin-graphs, Acta Mathematica Sinica, Chinese Series, 2007, 50(1): 197-204. Cop y ri g ht © 2012 SciRes.99 |