On the Spectra of Chromatic Number and Chromatic Index of Cyclic Covers

Abstract

For a fixed integer $\ell \ge 2$, we study what values of chromatic index and chromatic number can be attained by some $\ell$-fold cyclic cover of a loopless multigraph. For edge-coloring, we first investigate the density, a fundamental lower bound for the chromatic index, and show that the density of every $\ell$-fold cyclic cover of a graph $G$ is at most that of $G$. We further prove that if $\ell$ is even, then the spectrum of chromatic indices over all $\ell$-fold cyclic covers of $G$ contains every integer between $\Delta (G)$ and ${\chi }^{\prime }(G)$. When $\ell$ is odd, the chromatic-index spectrum need not be complete in general; for edge-chromatic critical graphs, we determine exactly which values are attainable. For vertex-coloring, we prove that if $\chi (G)\ge 3$, then the spectrum of chromatic numbers over all $\ell$-fold cyclic covers of $G$ contains every integer between $3$ and $\chi (G)$. Moreover, this spectrum contains $2$ if and only if $G$ is bipartite or $\ell$ is even.

15 pages, 2 tables, 1 figure