# Equitable Coloring on Total Graph of Bigraphs and Central Graph of Cycles and Paths

Authors: J. Vernold Vivin; K. Kaliraj; M. M. Akbar Ali
Journal: International Journal of Mathematics and Mathematical Sciences
 (2011)

---

## Abstract

The notion of equitable coloring was introduced by Meyer in 1973. In this
paper we obtain interesting results regarding the equitable chromatic numberχ= for the total graph of complete bigraphs T(Km,n), the central graph of cycles C(Cn) and the central graph of paths C(Pn).


---

## Body

## 1. Introduction

The central graph [1, 2] C(G) of a graph G is formed by adding an extra vertex on each edge of G, and then joining each pair of vertices of the original graph which were previously nonadjacent.The total graph [3, 4] of G has  vertex set V(G)∪E(G) and edges joining all elements of this vertex set which are adjacent or incident in G.If the set of vertices of a graphG can be partitioned into k classes V1,V2,…,Vk such that each Vi is an independent set and the condition ||Vi|-|Vj||≤1 holds for every pair (i,j), then G is said to be equitably k-colorable. The smallest integer k for which G is equitable k-colorable is known as the equitable chromatic number [5–10] of G and denoted by χ=(G). Additional graph theory terminology used in this paper can be found in [3, 4].


## 2. Equitable Coloring on Total Graph of Complete Bigraphs

Theorem 2.1.
Ifm≤n, the equitable chromatic number of total graph of complete bigraphs Km,n,
(2.1)χ=(T(Km,n))={n+1ifm<n,n+2ifm=n.Proof.
Let(X,Y) be the bipartition of Km,n, where X={vi:1≤i≤m} and Y={vj′:1≤j≤n}. Let uij(1≤i≤m;1≤j≤n) be the edges of vivj′. By the definition of total graph, T(Km,n) has the vertex set {vi:1≤i≤m}∪{vj′:1≤j≤n}∪{uij:1≤i≤m,1≤j≤n} and the vertices {uij:1≤i≤m,1≤j≤n} induce n disjoint cliques of order n in T(Km,n). Also vi(1≤i≤m) is adjacent to vj′(1≤j≤n).Case 1 (ifm=n, χ=(T(Km,n))=n+2).
Now we partition the vertex setV(T(Km,n)) as follows:
(2.2)V1={u11,u2n,u3(n-1),u4(n-2),…,u(n-1)3,un2},V2={u12,u21,u3n,u4(n-1),…,u(n-1)4,un3},⋮Vn={u1n,u2(n-1),u3(n-2),u4(n-3),…,u(n-1)3,un1},Vn+1={v1,v2,…,vn},Vn+2={v1′,v2′,…,vn′}.
Clearly V1,V2,…,Vn+2 are independent sets and |Vi|=n(1≤i≤n+2) satisfying the condition ||Vi|-|Vj||=0, for any i≠j, χ=(T(Km,n))≤n+2. Since there exists a clique of order n+1 in T(Km,n). χ(T(Km,n))≥n+1, also each vi of T(Km,n) receives one color different from the color class assigned to the clique induced by {uij:1≤i≤m;1≤j≤n}. By the definition of total  graph, each vi is adjacent with vj′(1≤j≤n). Therefore, {v1,v2,…,vm} and {v1′,v2′,…,vn′} are independent sets and hence χ(T(Km,n))≥n+2. That is, χ=(T(Km,n))≥χ(T(Km,n))≥n+2; therefore χ=(T(Km,n))≥n+2. Hence χ=(T(Km,n))=n+2.Case 2 (ifm<n, χ=(T(Km,n))=n+1).
Now we partition the vertex setV(T(Km,n)) as follows:
(2.3)V1={u11,u22,u33,u44,…,umm}∪{vn′},V2={u12,u23,u34,…,um(m-1)}∪{um1}∪{v1′},V3={u13,u24,u35,…,um(m-2)}∪{u(m-1)3,um2}∪{v2′},⋮Vn-1={u1(n-1),u2n}∪{u31,u32,…,um(m-2)}∪{vn-2′},Vn={u1n}∪{u21,u32,…,um(m-1)}∪{vn-1′},Vn+1={v1,v2,v3,…,vm}.
Clearly V1,V2,…,Vn+1 are independent sets of T(Km,n). Also |V1|=|V2|=⋯=|Vn|=m+1 and |Vn+1|=m satisfy the condition ||Vi|-|Vj||≤1, for any i≠j, χ=(T(Km,n))≤n+1. Since there exists a clique of order n+1 in T(Km,n). χ(T(Km,n))≥n+1, that is, χ=(T(Km,n))≥χ(T(Km,n))≥n+1, therefore χ=(T(Km,n))≥n+1. Hence χ=(T(Km,n))=n+1.


## 3. Equitable Coloring on Central Graph of Cycles and Paths

Theorem 3.1.
Ifn≥5, the equitable chromatic number of central graph of cycles Cn,
(3.1)χ=(C(Cn))={n+12ifnisodd,n2ifniseven.Proof.
LetV(Cn)={v1,v2,…,vn} and E(Cn)={e1,e2,…,en} be the vertices and edges of Cn taken in the cyclic order. By the definition of central graph, C(Cn) has the vertex set V(Cn)∪{ui:1≤i≤n}, where ui is the vertex of subdivision of the edge ei and joining all the nonadjacent vertices of Cn in C(Cn).Case 1 (n is odd).
We partition the vertex setV(C(Cn)) as
(3.2)V1={v1,v2,un-2,un-1},V2={v3,v4,un},V3={v5,v6,u1,u2},V4={v7,v8,u3,u4},⋮V(n-1)/2={vn-2,vn-1,un-6,un-5},V(n+1)/2={vn,un-4,un-3}.
Clearly V1,V2,…V(n-1)/2,V(n+1)/2 are independent sets of C(Cn). Also |V1|=|V3|=|V4|=⋯=|V(n-1)/2|=4 and |V2|=|V(n+1)/2|=3. The inequality ||Vi|-|Vj||≤1 holds, for any i≠j, χ=(C(Cn))≤(n+1)/2. For each i, vi is nonadjacent with vi-1 and vi+1 and hence χ(C(Cn))≥(n+1)/2. That is, χ=C(Cn)≥χ(C(Cn))≥(n+1)/2, χ=(C(Cn))≥(n+1)/2. Therefore, χ=(C(Cn))=(n+1)/2.Case 2 (n is even).
Now we partition the vertex setV(C(Cn)) as follows:
(3.3)V1={v1,v2,un-3,un-2},V2={v3,v4,un-1,un},V3={v5,v6,u1,u2},V4={v7,v8,u3,u4},⋮Vn/2={vn-1,vn,un-5,un-4}.
Clearly V1,V2,…Vn/2 are independent sets of C(Cn). Also |V1|=|V2|=|V3|=|V4|=⋯=|Vn/2|=4. The inequality ||Vi|-|Vj||=0 holds, for any i≠j, χ=(C(Cn))≤n/2. For each i, vi is nonadjacent with vi-1 and vi+1 and hence χ(C(Cn))≥n/2. That is, χ=C(Cn)≥χ(C(Cn))≥n/2, χ=(C(Cn))≥n/2. Therefore, χ=(C(Cn))=n/2.Remark 3.2.
Ifn=3,4, then χ=(C(Cn))=2,3, respectively.Theorem 3.3.
Ifn≥5, the equitable chromatic number of central graph of paths Pn,
(3.4)χ=(C(Pn))={n+12ifnisodd,n2ifniseven.Proof.
LetV(Pn)={v1,v2,…,vn} and E(Pn)={e1,e2,…,en} be the vertices and edges of Pn. By the definition of central graph, C(Pn) has the vertex set V(Pn)∪{ui:1≤i≤n-1}, where ui is the vertex of subdivision of the edge ei and joining all nonadjacent vertices of Pn in C(Pn).Case 1 (n is odd).
Now we partition the vertex setV(C(Pn)) as follows:
(3.5)V1={v1,v2,un-2},V2={v3,v4,un-1},V3={v5,v6,u1,u2},V4={v7,v8,u3,u4},⋮V(n-1)/2={vn-1,vn-2,un-6,un-5},V(n+1)/2={vn,un-4,un-3}.
Clearly V1,V2,…V(n-1)/2,V(n+1)/2 are independent sets of C(Pn). Also |V3|=|V4|=⋯=|V(n-1)/2|=4 and |V1|=|V2|=|V(n+1)/2|=3. The inequality ||Vi|-|Vj||≤1 holds, for any i≠j, χ=(C(Pn))≤(n+1)/2. For each i, vi is nonadjacent with vi-1 and vi+1 and hence χ(C(Pn))≥(n+1)/2. That is, χ=C(Pn)≥χ(C(Pn))≥(n+1)/2, χ=(C(Pn))≥(n+1)/2. Therefore χ=(C(Pn))=(n+1)/2.Case 2 (n is even).
Now we partition the vertex setV(C(Pn)) as follows:
(3.6)V1={v1,v2,un-3,un-2},V2={v3,v4,un-1},V3={v5,v6,u1,u2},V4={v7,v8,u3,u4},⋮Vn/2={vn-1,vn,un-5,un-4}.
Clearly V1,V2,…Vn/2 are independent sets of C(Pn). Also |V1|=|V3|=|V4|=⋯=|Vn/2|=4 and |V2|=3. The inequality ∥Vi|-|Vj∥≤1 holds for any i≠j, χ=(C(Pn))≤n/2. For each i, vi is nonadjacent with vi-1 and vi+1 and hence χ(C(Pn))≥n/2. That is, χ=C(Pn)≥χ(C(Pn))≥n/2, χ=(C(Pn))≥n/2. Therefore, χ=(C(Pn))=n/2.Remark 3.4.
Ifn=1,2,3,4, then χ=(C(Pn))=1,2,3,3, respectively.



---

*Source: 279246-2011-04-12.xml*