2026/08/03 by Guantao Chen, Hein van der Holst, Rong Luo +1
Mathematics · #math.CO #msc:05C15 #msc:05C25
15 pages, 2 tables, 1 figure
arxiv created 2026/08/03 · arxiv updated 2026/08/05
For a fixed integer ℓ ≥ 2, we study what values of chromatic index and chromatic number can be attained by some ℓ-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 ℓ-fold cyclic cover of a graph G is at most that of G. We further prove that if ℓ is even, then the spectrum of chromatic indices over all ℓ-fold cyclic covers of G contains every integer between Δ(G) and χ'(G). When ℓ 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 χ(G)≥ 3, then the spectrum of chromatic numbers over all ℓ-fold cyclic covers of G contains every integer between 3 and χ(G). Moreover, this spectrum contains 2 if and only if G is bipartite or ℓ is even.