On graphs with girth at least five achieving Steffen’s edge coloring bound
Guantao Chen 1, Alireza Fiujlaali 1, Anna Johnsen-Yu 1,2, Jessica McDonald 3 · 2026
Read On graphs with girth at least five achieving Steffen’s edge coloring bound by Guantao Chen 1, Alireza Fiujlaali 1, Anna Johnsen-Yu 1,2, Jessica McDonald 3 (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-23274.txt.
Description
Guantao Chen and three co-authors study edge coloring in graphs with no short cycles. Vizing and Gupta bounded the chromatic index, the number of colors needed for edges, by the maximum degree plus the maximum multiplicity. Steffen proposed a sharper bound that some graphs achieve.
The authors focus on graphs whose girth, the length of the shortest cycle, is at least five. They examine which such graphs reach Steffen's bound exactly. Edge coloring results support scheduling and network design, where edges are tasks needing distinct slots. Maximum degree and maximum multiplicity set the classical ceiling that Steffen's sharper bound tries to lower.
Catalog record
| CREATOR | Guantao Chen 1, Alireza Fiujlaali 1, Anna Johnsen-Yu 1,2, Jessica McDonald 3 |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 46 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-23274