Achieving maximum chromatic index in multigraphs

Let GG be a multigraph with maximum degree ΔΔ and maximum edge multiplicity μμ. Vizing’s Theorem says that the chromatic index of GG is at most Δ+μΔ+μ. If GG is bipartite its chromatic index is well known to be exactly ΔΔ. Otherwise GG contains an odd cycle and, by a theorem of Goldberg, its chromatic index is at most Δ+1+Δ−2go−1, where gogo denotes odd-girth. Here we prove that a connected GG achieves Goldberg’s upper bound if and only if G=μCgoG=μCgo and (go−1)∣2(μ−1)(go−1)∣2(μ−1). The question of whether or not GG achieves Vizing’s upper bound is NP-hard for μ=1μ=1, but for μ≥2μ≥2 we have reason to believe that this may be answerable in polynomial time. We prove that, with the exception of μK3μK3, every connected GG with μ≥2μ≥2 which achieves Vizing’s upper bound must contain a specific dense subgraph on five vertices. Additionally, if Δ≤μ2Δ≤μ2, we prove that GG must contain K5K5, so GG must be nonplanar. These results regarding Vizing’s upper bound extend work by Kierstead, whose proof technique influences us greatly here.