Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6424056 | European Journal of Combinatorics | 2016 | 19 Pages |
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:=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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
H.A. Kierstead, David A. Smith, W.T. Trotter,