5 papers · 1 filter
Online Graph Coloring: Competitive Ratios Separating Randomized and Deterministic Algorithms
Ken-ichi Kawarabayashi, Hirotaka Yoneda, Masataka Yoneda
We study online coloring, focusing on the competitive ratio. The best previously known results were (1) a lower bound of for both deterministic and randomized alg…
The Balanced Four-Color Theorem
Ken-ichi Kawarabayashi, Hirotaka Yoneda, Masataka Yoneda
We show that every planar graph with vertices admits a 4-coloring in which each color is used on fewer than vertices. This bound is the best possible. Moreover, su…
Online Coloring for Graphs of Large Odd Girth
Hirotaka Yoneda, Masataka Yoneda
We study the problem of online coloring for graphs with large odd girth. The best previously known algorithm uses colors, which was discovered by Kierstead in 1998. Th…
Online Graph Coloring for -Colorable Graphs
Ken-ichi Kawarabayashi, Hirotaka Yoneda, Masataka Yoneda
We study the problem of online graph coloring for -colorable graphs. The best previously known deterministic algorithm uses colors for genera…
Better coloring of 3-colorable graphs
Ken-ichi Kawarabayashi, Mikkel Thorup, Hirotaka Yoneda
We consider the problem of coloring a 3-colorable graph in polynomial time using as few colors as possible. This is one of the most challenging problems in graph algorithms. In thi…