Problem

Source: 2021 China TST, Test 2, Day 1 P2

Tags: graph theory, Graph coloring, combinatorics



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$.