Equitable colorings of Cartesian products of graphs ?
The present paper studies the following variation of vertex coloring on graphs. A graph G G is equitably k k -colorable if there is a mapping f:V(G)?{1,2,,k} f : V ( G ) ? { 1 , 2 ,  , k } such that f(x)?f(y) f ( x ) ? f ( y ) for xy?E(G) x y ? E ( G ) and ??f?1(i)???f?1(j)???1 ? ? f ? 1 ( i ) ? ? ? f ? 1 ( j ) ? ? ? 1 for 1?i,j?k 1 ? i , j ? k . The equitable chromatic number of a graph G G , denoted by ?=(G) ? = ( G ) , is the minimum k k such that G G is equitably k k -colorable. The equitable chromatic threshold of a graph G G , denoted by ? = ? ( G ) , is the minimum t t such that G G is equitably k k -colorable for all k?t k ? t . Our focus is on the equitable colorability of Cartesian products of graphs. In particular, we give exact values or upper bounds of ?=(G?H) ? = ( G ? H ) and ? = ? ( G ? H ) when G G and H H are cycles, paths, stars, or complete bipartite graphs.
equitable coloring cartesian product equitable chromatic number equitable chromatic threshold