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
| CREATOR | Hirotaka Yoneda, Masataka Yoneda |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 44439 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.27690