Online Graph Coloring for k k -Colorable Graphs
Ken-ichi Kawarabayashi, Hirotaka Yoneda, Masataka Yoneda · 2025
Read Online Graph Coloring for k k -Colorable Graphs by Ken-ichi Kawarabayashi, Hirotaka Yoneda, Masataka Yoneda (2025) 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-2511-16100.txt.
Introduction
Ken-ichi Kawarabayashi, Hirotaka Yoneda, and Masataka Yoneda break a nearly thirty-year barrier in online graph coloring. Online coloring assigns colors to vertices as they arrive, using as few colors as possible, for graphs guaranteed to be colorable with a given number of colors. The best deterministic bounds had stood since 1998, especially weak for large color budgets and for the four-colorable case.
For graphs needing at least five colors, their deterministic algorithm uses far fewer colors than the old bound, with an exponent depending on pairs of colors rather than factorials. For four-colorable graphs they improve the exponent further. For bipartite graphs, they pin down the randomized optimum within a small factor, giving matching upper and lower logarithmic bounds.
Catalog record
| CREATOR | Ken-ichi Kawarabayashi, Hirotaka Yoneda, Masataka Yoneda |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 154 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-16100