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

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