On the performance of the first-fit coloring algorithm on permutation graphs
In this paper we study the performance of a particular on-line coloring algorithm, the First-Fit or Greedy algorithm, on a class of perfect graphs namely the permutation graphs. We prove that the largest number of colors chi (FF)(G) that the First-Fit coloring algorithm (FF) needs on permutation graphs of chromatic number chi>(*) over bar * (G) = chi when taken over all possible vertex orderings is not linearly bounded in terms of the off-line optimum, if X is a fixed positive integer. Specifically, we prove that for any integers chi > 0 and k greater than or equal to 0, there exists a permutation graph G on n vertices such that chi>(*) over bar * (G) = chi and chi (FF)(G) greater than or equal to 1/2 ((chi (2) + chi) + k(chi (2) - chi)), for sufficiently large n. Our result shows that the class of permutation graphs P is not First-Fit X-bounded; that is, there exists no function f such that for all graphs G epsilon P, chi (FF)(G) less than or equal to f(omega>(*) over bar * (G)). Recall that for perfect graphs omega>(*) over bar * (G) = chi>(*) over bar * (G), where omega>(*) over bar * (G) denotes the clique number of G. (C) 2000 Elsevier Science B.V. All rights reserved.
algorithms permutation graphs on-line coloring perfect graphs first-fit algorithm combinatorial problems