Online Coloring for Graphs of Large Odd Girth

Hirotaka Yoneda, Masataka Yoneda · 2026

Read Online Coloring for Graphs of Large Odd Girth by Hirotaka Yoneda, Masataka Yoneda (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-2604-27690.txt.

Description

Hirotaka Yoneda and Masataka Yoneda study online coloring of graphs with large odd girth. The best prior method, from Kierstead in 1998, uses on the order of square-root-of-n colors and needs odd girth of at least 7. The authors show that for any small positive exponent, graphs with large odd girth can be deterministically colored online with on the order of n-to-that-exponent colors. Their result pushes online coloring far beyond the square-root bound for graphs of large odd girth.

Catalog record

CREATORHirotaka Yoneda, Masataka Yoneda
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE44439
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.27690

Browse the full library · About the Tower of Babel