The b-Chromatic Number of Corona Graphs

Abstract

A b-coloring of a graph G is a proper coloring of the vertices of G such that there exists a vertex in each color class joined to at least one vertex in each other color class. The b-chromatic number of a graph G, denoted by φ(G), is the maximal integer k such that G may have a b-coloring with k colors. This parameter has been defined by Irving and Manlove [5]. They proved that determining φ(G) is NPhard in general and polynomial for trees. In this paper, we find that the b-chromatic number on corona graph of any graph G with path P _n, cycle C _n and complete graph K _n. Finally, we generalized the b-chromatic number on corona graph of any two graphs, each one on n vertices.