DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2026.127

Online Coloring for Graphs of Large Odd Girth

Authors: Hirotaka Yoneda and Masataka Yoneda

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract

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.

Cite as

Hirotaka Yoneda and Masataka Yoneda. Online Coloring for Graphs of Large Odd Girth. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 127:1-127:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{yoneda_et_al:LIPIcs.ESA.2026.127,
  author =	{Yoneda, Hirotaka and Yoneda, Masataka},
  title =	{{Online Coloring for Graphs of Large Odd Girth}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{127:1--127:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.127},
  URN =		{urn:nbn:de:0030-drops-272633},
  doi =		{10.4230/LIPIcs.ESA.2026.127},
  annote =	{Keywords: online coloring, online algorithms, graph theory, graph coloring, odd girth}
}

Search Results

Documents authored by Yoneda, Hirotaka

Online Coloring for Graphs of Large Odd Girth

Abstract

Cite as

Thanks for your feedback!

Could not send message