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

CREATORGuantao Chen 1, Alireza Fiujlaali 1, Anna Johnsen-Yu 1,2, Jessica McDonald 3
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE46 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-23274

Browse the full library · About the Tower of Babel