Equitable Chromatic Numbers of Derived Graph of Particular Graphs.

Abstract

An equitable k-coloring is a proper coloring with color classes V_1,V_2,\ldots,V_{k} for which the numbers of vertices in any two color classes differ by at most one. A graph G is equitably k-colorable if there is an equitable k-coloring. The smallest positive integer k such that G is equitably k-colorable is the equitable chromatic number of G, denoted by \chi_{=}(G). The derived graph of a simple graph, denoted by G^+, is the graph having the same vertex set as G, in which two vertices are adjacent if and only if their distance in G is two. In this paper, we determine the exact values of the equitable chromatic number of the derived graph of paths, cycles, wheel graphs, helm graphs, sunlet graphs, and tadpole graphs.