Equitable Chromatic Threshold of Direct 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_m^*(G)\), is the minimum \(k\) such that \(G\) is equitably \(k’\)-colorable for all \(k’ > k\). Let \(G \times H\) denote the direct product of graphs \(G\) and \(H\). For \(n \geq m \geq 2\), we prove that \(\chi_m^*(K_m \times K_n)\) equals \(\left\lceil \frac{mn}{m+1} \right\rceil\) if \(n \equiv 2, \ldots, m \pmod{m+1}\), and equals \(m\left\lceil \frac{n}{s^*} \right\rceil\) if \(n \equiv 0, 1 \pmod{m+1}\), where \(s^*\) is the minimum positive integer such that \(s^* \nmid n\) and \(s^* \geq m+2\).