On-Line and First-fit Coloring of Graphs that Do Not Induce $P_5 $
Henry A. Kiersteád, Stephen G. Penrice, William T. Trotter · SIAM Journal on Discrete Mathematics · 1995
For a graph H, let ${\text{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 Gyárfás and Lehel. First, we show that there exists a function $f( \omega )$ such that for any graph $G \in \,{\text{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 that there exists an on-line algorithm A that will color any graph $G \in \,{\text{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.