Let $G$ be a graph of order $n$ with $m$ edges. Color each vertices uniformly at random with $q$ colors. It is easy to see that expected number of monochromatic edges (edge whose end vertices are of same color) equal to $\frac{m}{q}$. Let $t \leq \frac{m}{q}$, is it possible to show (assuming $q= o(m)$)
$$
\mathbb{P}(\text{Monochromatic edges} \leq t)\leq e^{t-c\frac{m}{q}(1+o(1))}
$$
where $c$ is an absolute constant. I tried using Janson's inequality but was unsuccessful. 



Concentration of monochromatic edges in a graph
Such an estimate cannot hold in general. Here are two different counterexamples:


1. Consider a complete bipartite graph with $n/2$ nodes on each side and $m=n^2/4$ edges.
Take $q$ bounded, e.g. $q=2$. Then for $q=2$, with probability $2^{-n}$ all left nodes are blue and all right nodes are red, so there are no monochromatic edges.
2. Consider $q$ large and let $m=(q\log q)/2$.
Let $G$ be a star on $n=m+1$ nodes. By a standard coupon collector argument. with probability tending to 1, the $m$ nodes of the star leave $q^{1/2}(1+o(1)$ colors unused; if the central node takes ones of these colors, then there are no monochromatic edges. This has probability $q^{-1/2}(1+o(1)$.


