Volume :8 , Issue :1 ,Page :30-41

Abstract :A strong k-coloring is a proper k-coloring in which all the color classes are of same size. For sets to have equal size, k ቒ ௡ ௞ ቓ – n isolated vertices are added. An r co-coloring of a graph is a partition of the vertex set into r sets such th at each set in the partition is eith er an independent set or induces a clique, where empty sets are permitte d in the partition. Combining thes e two concepts, in this paper a new graph partition called strong co-coloring is define d. A strong r co-coloring is a partition of the vertex set into r sets of equal size in which each set in the partition is either an independent set or induces a clique and (if necessary) k ቒ ௡ ௞ ቓ – n isolated vertices are added . The new graph parameter called the strong co-chromatic number of a graph G is the least r for which G has a strong r co-coloring. In this paper, exact bounds of stro ng co-chromatic number of some well-known graphs are found.