Effective on-line coloring of \(P_ 5\)-free graphs (Q1180418)

In the on-line graph coloring problem the adversary feeds the algorithm one vertex at a time which must be irrevocably assigned a color. The most common on-line coloring algorithm is the first fit (FF) algorithm that at each step assigns the smallest possible color to the current vertex of the graph. FF finds a chromatic coloring of any \(P_ 4\)-free graph and demonstrates a good performance ratio for \(P_ 5\)-free graphs. In the note the authors study another on-line algorithm that colors any \(P_ 5\)-free graph with \(f(w)\) colors, where \(f\) is a function of the clique number \(w\) of the graph.