Equitable chromatic threshold of Kronecker products of complete graphs

Abstract

A proper vertex coloring of a graph is equitable if the sizes of color classes differ by at most 1. The equitable chromatic threshold of a graph $G$, denoted by ${\chi }_{=}^{\ast }(G)$, is the minimum $k$ such that $G$ is equitably $k^{\prime }$-colorable for all $k^{\prime }\ge k$. Let $G\times H$ denote the direct product of graphs $G$ and $H$. For $n\ge m\ge 2$ we prove that ${\chi }_{=}^{\ast }(K_m\times K_n)$ equals $\lceil \frac{mn}{m+1}\rceil$ if $n\equiv 2,...,m(\text{mod}m+1)$, and equals $m\lceil \frac{n}{s^{\star }}\rceil$ if $n\equiv 0,1(\text{mod}m+1)$, where $s^{\star }$ is the minimum positive integer such that $s^{\star }\nmid n$ and $s^{\star }\ge m+2.$

The Primary Category is not correct. We would like to resubmit it

Cited by in corpus (1)

• Equitable coloring of Kronecker products of complete multipartite graphs and complete graphs