2026-09-21T17:23:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27263 2026-09-05T20:17:06Z ddc:004 open_access

Online Coloring for Graphs of Large Odd Girth Yoneda, Hirotaka Yoneda, Masataka online coloring online algorithms graph theory graph coloring odd girth 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 ε > 0, there exists a constant g' ∈ {3, 5, 7, …} such that graphs with odd girth at least g' can be deterministically colored online using O(n^ε) colors. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hirotaka Yoneda and Masataka Yoneda 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.127 urn:nbn:de:0030-drops-272633 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.127 eng https://creativecommons.org/licenses/by/4.0/legalcode