ONLINE AND FIRST-FIT COLORING OF GRAPHS THAT DO NOT INDUCE P-5

For a graph H, let Forb(H) be the class of graphs that do not induce H , and let P-5 be the path on five vertices. In this article, we answer two questions of Gyarfas and Lehel. First, we show that there exists a function f(omega) such that for any graph G is an element of Forb(P- 5), the on-line coloring algorithm First-Fit uses at most f(omega(G)) colors on G, where omega(G) is the clique size of G. Second, we show t hat there exists an on-line algorithm A that will color any graph G is an element of Forb(P-5) with a number of colors exponential in omega( G). Finally, we extend some of our results to larger classes of graphs defined in terms of a list of forbidden subgraphs.