Abstract
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 \(\frac{\omega(G)}{8}\).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Chrobak, M., Ślusarek, M.: On some packing problems related to dynamic storage allocation. RAIRO Inform. Theor. Appl. 22, 487–499 (1988)
Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic, London (1980)
Kierstead, H.A., Qin, J.: Coloring interval graphs with first-fit. Discrete Math. 144, 47–57 (1995)
Kierstead, H.A.: The linearity of first-fit coloring of interval graphs. SIAM J. Discrete Math. 1(4), 526–530 (1988)
Varadarajan, K., Pemmaraju, S.V., Raman, R.: Buffer minimization using max-coloring. In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium On Discrete Algorithms, pp. 562–571, New Orleans, 11–14 January 2004
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Narayanaswamy, N.S., Babu, R.S. A Note on First-Fit Coloring of Interval Graphs. Order 25, 49–53 (2008). https://doi.org/10.1007/s11083-008-9076-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11083-008-9076-6