On $b$-Coloring of Cartesian Product of Graphs

Abstract

A $b$-coloring of a graph $G$ by $k$ colors is a proper $k$-coloring of the vertices of $G$ such that in each color class there exists a vertex having neighbors in all the other $k-1$ color classes. The $b$-chromatic number $\phi (G)$ of a graph $G$ is the maximum $k$ for which $G$ has a $b$-coloring by $k$ colors. This concept was introduced by R.W. Irving and D.F. Manlove in $1999$. In this paper, we study the $b$-chromatic numbers of the cartesian products of paths and cycles with complete graphs and the cartesian product of two complete graphs.