EQUITABLE COLORING OF PRISMS AND THE GENERALIZED PETERSEN GRAPHS

Gallian in 2007 gave the construction of the prism Y_m^n by considering the cartesian product of the cycle C_m and the path P_n. The generalized Petersen graph was introduced in 1950 by Coxeter. The generalized Petersen graphs are a family of cubic graphs formed by connecting the vertices of a regular polygon to the corresponding vertices of a star polygon. A graph G is said to be equitable k-coloring if the vertex set V(G) is partitioned into disjoint independent sets so that the size of each partition differs at most one by the rest of the partitions. In this paper, we discussed the equitable coloring of the prisms and obtained the result that its chromatic number always lies between 2 and 3. We have also discussed the equitable coloring of the generalized Petersen graphs P(m,n),m?2n+1,n>1.