First-fit coloring on interval graphs has performance ratio at least 5

Henry Kierstead, David A. Smith, W. T. Trotter

Research output: Contribution to journalArticlepeer-review

15 Scopus citations


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:=supGχ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.

Original languageEnglish (US)
Pages (from-to)236-254
Number of pages19
JournalEuropean Journal of Combinatorics
StatePublished - Jan 1 2016

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'First-fit coloring on interval graphs has performance ratio at least 5'. Together they form a unique fingerprint.

Cite this