On-line coloring of geometric intersection graphs

AbstractThis paper studies on-line coloring of geometric intersection graphs. It is shown that no deterministic on-line algorithm can achieve competitive ratio better than Ω(logn) for disk graphs and for square graphs with n vertices, even if the geometric representation is given as part of the input. Furthermore, it is proved that the standard First-fit heuristic achieves competitive ratio O(logn) for disk graphs and for square graphs and is thus best possible