Online Coloring for Graphs of Large Odd Girth
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909004157943808 |
|---|---|
| author | Yoneda, Hirotaka Yoneda, Masataka |
| author_facet | Yoneda, Hirotaka Yoneda, Masataka |
| contents | We study the problem of online coloring for graphs with large odd girth. The best previously known algorithm uses $O(n^{1/2})$ colors, which was discovered by Kierstead in 1998. This algorithm works when the odd girth is 7 or more. In this paper, we provide the following: for every $\varepsilon > 0$, there exists a constant $g' \in \{3, 5, 7, \dots\}$ such that graphs with odd girth at least $g'$ can be deterministically colored online using $O(n^{\varepsilon})$ colors. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_27690 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Online Coloring for Graphs of Large Odd Girth Yoneda, Hirotaka Yoneda, Masataka Data Structures and Algorithms We study the problem of online coloring for graphs with large odd girth. The best previously known algorithm uses $O(n^{1/2})$ colors, which was discovered by Kierstead in 1998. This algorithm works when the odd girth is 7 or more. In this paper, we provide the following: for every $\varepsilon > 0$, there exists a constant $g' \in \{3, 5, 7, \dots\}$ such that graphs with odd girth at least $g'$ can be deterministically colored online using $O(n^{\varepsilon})$ colors. |
| title | Online Coloring for Graphs of Large Odd Girth |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2604.27690 |