Tight Bounds for Online Coloring of Basic Graph Classes

Susanne Albers, Sebastian Schraink

We resolve a number of long-standing open problems in online graph coloring. More specifically, we develop tight lower bounds on the performance of online algorithms for fundamenta…