Colorings of covers of graphs Let $G$ be a finite graph.  Let $Cov_k(G)$ be the set of all $k$-sheeted covers of $G$.  Note that if $G$ is $\chi$-colorable, then so is every graph in $Cov_k(G)$.  I am wondering how the average chromatic number of the elements in $Cov_k(G)$ behaves as $k \to \infty$. As a concrete question: let $Cov_k(G, m)$ be the set of $k$-coverings of $G$ that are $m$ colorable.  Does the limit 
$$
\lim_{k \to \infty} \frac{|Cov_k(G, m)|}{|Cov_k(G)|}
$$
ever equal 1 for $m$ less than the chromatic number of $G$.  
 A: This can happen for some graphs $G$.
A particularly easy case to analyze is $G = K_n$. For $n \ge 4$, the chromatic number of a $k$-sheeted cover of $K_n$ can be bounded by Brooks's theorem: the cover is $(n-1)$-regular, so it has chromatic number $n$ exactly when it has a $K_n$ component, and chromatic number at most $n-1$ otherwise.
However, almost no $k$-sheeted covers of $K_n$ have a $K_n$ component (and so almost all are $(n-1)$-colorable). Consider the following probabilistic model: we take $n$ sets of $k$ vertices each, and obtain a $k$-sheeted cover of $K_n$ by choosing a uniformly random matching between every two sets. Then there are $k^n$ possible choices of a vertex from each set, and each such choice forms a $K_n$ component with probability $k^{-\binom n2}$. Therefore the expected number of $K_n$ components is $k^{n - \binom n2}$, which goes to $0$ as $k \to \infty$.
On the other hand, when $n=3$, almost all $k$-sheeted covers of $K_3$ have chromatic number $3$. Here, the expected number of $K_3$ components is $1$, but that's not the problem; the problem is that all the components are cycles whose length is a multiple of $3$, and it is very unlikely (and, for some $k$, impossible) for all these cycles to be even. As soon as a single component is an odd cycle, we have chromatic number $3$.
