COLORING INDUCTIVE GRAPHS ONLINE

In this paper we consider the problem of on-line graph coloring. In an instance of on-line graph coloring, the nodes are presented one at a time. As each node is presented, its edges to previously presented nodes are also given. Each node must be assigned a color, different from the colors of its neighbors, before the next node is given. Let A(G) be the number of colors used by algorithm A on a graph G and let chi(G) be the chromatic number of G. The performance ratio of an on-line graph coloring algorithm for a class of graphs l is max(G epsilon l),(A(G)/%(G)). We consider the class of d-inductive graphs. A graph G is d-inductive if the nodes of G can be numbered so that each node has at most d edges to higher-numbered nodes. In particular, planar graphs are 5-inductive, and chordal graphs are chi(G)-inductive. First Fit is the algorithm that assigns each node the lowest-numbered color possible. We show that if G is d-inductive, then First Fit uses O(d log n) colors on G. This yields an upper bound of O(log n) on the performance ratio of First Fit on chordal and planar graphs. First Fit does as well as any on-line algorithm for d-inductive graphs: we show that, for any d and any on-line graph coloring algorithm A, there is a d-inductive graph that forces A to use Omega(d log n) colors to color G. We also examine on-line graph coloring with lookahead. An algorithm is on-line with lookahead I, if it must color node i after examining only the first l + i nodes. We show that, for l < n/log n, the lower bound of d log n colors still holds.