A Note on First-Fit Coloring of Interval Graphs

We apply the Column Construction Method (Varadarajan et al., Proceedings of the Fifteenth Annual ACM-SIAM Symposium On Discrete Algorithms, pp. 562–571, 2004) to a minimal clique cover of an interval graph to obtain a new proof that First-Fit is 8-competitive for online coloring interval graphs. This proof also yields a new discovery that in each minimal clique cover of an interval graph G, there is a clique of size .