Skip to content

Author

Alireza Fiujlaali

1 paper indexed here

We haven’t gathered this author’s papers yet. Follow them and we’ll fetch their work.

Not the right person? Other researchers publish under this name.

Preprint Aug 2026

Odd-Girth Bounds for Defective Edge Coloring

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 $\chi'_d(G)$. Let $G$ be a loopless non-bipartite multigraph with maximum degree $\Delta(G)$ and odd girth $g_0(G)$, and let $d\ge1$ be odd. We prove that \[ \chi'_d(G)\le\left\lceil\frac{g_0(G)\Delta(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\ge3$, and every $\Delta>d$, an almost full ring multigraph $R(\Delta,g_0)$, an odd cycle with edge multiplicities alternating between $\lfloor\Delta/2\rfloor$ and $\lceil\Delta/2\rceil$, except that two consecutive edges have multiplicity $\lfloor\Delta/2\rfloor$, attains equality. We also derive a range in which the defective Goldberg--Seymour conjecture holds.

Guantao Chen, Alireza Fiujlaali · 0 citations