First-fit coloring on interval graphs has performance ratio at least 5

H. A. Kierstead, David A. Smith, W. T. Trotter

First-fit is the online graph coloring algorithm that considers vertices one at a time in some order and assigns each vertex the least positive integer not used already on a neighb…