Odd-Girth Bounds for Defective Edge Coloring

Abstract

A $(k,d)$-edge coloring of a loopless multigraph $G$ is an edge coloring using at most $k$ colors such that the subgraph formed by each color class has maximum degree at most $d$. The least such $k$ is denoted by $\ddot{I}{‡}_d^{\prime }(G)$. Let $G$ be a loopless non-bipartite multigraph with maximum degree $\hat{I}”(G)$ and odd girth $g_0(G)$, and let $d\ge 1$ be odd. We prove that \[ χ'_d(G)\le\left\lceil\frac{g_0(G)Δ(G)-1}{dg_0(G)-1}\right\rceil. \] For $d=1$, this is Goldberg's odd-girth refinement of Shannon's theorem, while for $g_0(G)=3$ it is the defective Shannon bound of Aboulker, Aubian, and Huang. For every odd $d>1$, every odd $g_0\ge 3$, and every $\hat{I}”>d$, an almost full ring multigraph $R(\hat{I}”,g_0)$, an odd cycle with edge multiplicities alternating between $\lfloor \hat{I}”/2\rfloor$ and $\lceil \hat{I}”/2\rceil$, except that two consecutive edges have multiplicity $\lfloor \hat{I}”/2\rfloor$, attains equality. We also derive a range in which the defective Goldberg--Seymour conjecture holds.

Submitted to The Electronic Journal of Combinatorics