CN-TST 2021 Problem 8

Given positive integers $n,k$ , $n \ge 2$ . Find the minimum constant $c$ satisfies the following assertion: For any positive integer $m$ and a $kn$ -regular graph $G$ with $m$ vertices, one could color the vertices of $G$ with $n$ different colors, such that the number of monochrome edges is at most $cm$ .