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
Telephone:[phone]
MA Ming
College of Mathematics and Computer Science
Northwest University for Nationalities
Lanzhou, Gansu, China 730030
Telephone:[phone]
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:
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 CmFn,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