\input zb-basic
\input zb-ioport
\iteman{io-port 05281948}
\itemau{Narayanaswamy, N.S.; Babu, R.Subhash}
\itemti{A note on first-fit coloring of interval graphs.}
\itemso{Order 25, No. 1, 49-53 (2008).}
\itemab
Summary: We apply the Column Construction Method [{\it K. Varadarajan}, {\it S. V. Pemmaraju}, and {\it S. Raman}, Buffer minimization using max-coloring, In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium On Discrete Algorithms, New Orleans, 11--14 January 2004, 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 $\frac{\omega(G)}{8}$.
\itemrv{~}
\itemcc{}
\itemut{first fit for online graph coloring; competitive analysis; column construction method}
\itemli{doi:10.1007/s11083-008-9076-6}
\end