Equitable colorings of Cartesian products of graphs

The present paper studies the following variation of vertex coloring on graphs. A graph GG is equitably kk-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)xy∈E(G) and ∣∣f−1(i)∣−∣f−1(j)∣∣≤1∣∣f−1(i)∣−∣f−1(j)∣∣≤1 for 1≤i,j≤k1≤i,j≤k. The equitable chromatic number of a graph GG, denoted by χ=(G)χ=(G), is the minimum kk such that GG is equitably kk-colorable. The equitable chromatic threshold of a graph GG, denoted by χ=∗(G), is the minimum tt such that GG is equitably kk-colorable for all k≥tk≥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 GG and HH are cycles, paths, stars, or complete bipartite graphs.