First-fit coloring on interval graphs has performance ratio at least 5
arXiv:1506.00192 · doi:10.1016/j.ejc.2015.05.015
Abstract
First-fit is the online graph coloring algorithm that considers vertices one at a time in some order and assigns each vertex the least positive integer not used already on a neighbor. The maximum number of colors used by first-fit on graph G over all vertex orders is denoted χ_{FF}(G). The exact value of R := \sup_G [χ_{FF}(G) / ω(G)] over interval graphs G is unknown. Pemmaraju, Raman, and Varadarajan (2004) proved R <= 10, and this can be improved to 8. Witsenhausen (1976) and Chrobak and Ślusarek (1988) showed R >= 4, and Ślusarek (1993) improved this to 4.45. We prove R >= 5.
arXiv commentAccepted to the European Journal of Combinatorics
Cited by in corpus (6)
- Online Coloring of Short Intervals
- Hummingbird: Fast, Flexible, and Fair Inter-Domain Bandwidth Reservations
- Batch Coloring of Graphs
- A tight analysis of Kierstead-Trotter algorithm for online unit interval coloring
- On-line partitioning of width w posets into w^O(log log w) chains
- On the Grundy number of Cameron graphs