Edge-coloring spectra of odd-fold graph covers and counterexamples to a conjecture

For a loopless multigraph G and an odd integer ≥3, let $Δ(G)$ be the maximum degree of G, let s₍G) be the minimum chromatic index of a cyclic -fold cover of G, and let {align*} L_(G):=max\{ Δ(G),\ max_{{S⊆ V(G)\\ |S|≥3 odd}} 2|E(G[S])|/|S|-1 \}. {align*} In this paper, we prove the sharp upper bound {align*} s_(G)≤max\{Δ(G)+1,L_(G)\}. {align*} For every nonempty bridgeless cubic graph H, we construct two 3-regular graphs, one a multigraph and the other a simple graph. In each case, the minimum chromatic indices over cyclic and over all -fold covers both equal the chromatic index of the multigraph obtained by replacing each edge of H with parallel edges. Taking H to be the Petersen graph gives both multigraph and simple graph counterexamples to a conjecture of Chen, van der Holst, Luo, and Ma, which asserts that s₍G)=L₍G) always holds. When G is connected and L₍G)>Δ(G), we determine the common spectrum of its connected cyclic and arbitrary -fold covers. We give polynomial-time algorithms to compute L₍G) and the spectrum endpoints. For fixed , we also construct in polynomial time a connected cyclic cover with any prescribed chromatic index in the spectrum.