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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.