Equitable colorings of Cartesian products with balanced complete multipartite graphs ?
A proper vertex coloring of a graph is equitable if the sizes of any two color classes differ by at most one. 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. Lin and Chang conjectured that for any (nontrivial) connected graphs G G and H H , ?=(G?H)??(G)?(H) ? = ( G ? H ) ? ? ( G ) ? ( H ) , where ? ? denotes the Cartesian product. In this paper, we prove the conjecture when G G or H H is a balanced complete multipartite graph. More precisely, we show a stronger result that for any graph H H with ?(H)?2 ? ( H ) ? 2 , ? = ( K r ( n ) ? H ) ? r ? ? ( H ) ? 1 r ? 1 ? , where r?2 r ? 2 , n?1 n ? 1 and Kr(n) K r ( n ) denotes the balanced complete r r -partite graph with part size n n .
equitable coloring cartesian product balanced complete multipartite graph equitable chromatic number