The Equitable Total Chromatic Number of Some Join graphs

doi:10.4236/ojapps.2012.24B023

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: [email protected]

Telephone:13909408935

MA Ming

College of Mathematics and Computer Science

Northwest University for Nationalities

Lanzhou, Gansu, China 730030

Email: [email protected]

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 averydifﬁcultproblem 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

Deﬁnition 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.

Deﬁnition 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.

Deﬁnition 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

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. Deﬁne 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.

Deﬁne 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.

Deﬁne 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

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.

Deﬁne 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.

Deﬁne 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

Deﬁne 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. Deﬁne fby

f(viuj)=i+j,i =0,1,··· ,n,j =1,2;

98 Cop

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.

Deﬁne 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).

Deﬁne 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:

[email protected]

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 SufﬁcientConditions 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