First-fit coloring on interval graphs has performance ratio at least 5
From MaRDI portal
Publication:499473
DOI10.1016/j.ejc.2015.05.015zbMath1321.05086arXiv1506.00192MaRDI QIDQ499473
David A. Smith, Henry A. Kierstead, William T. jun. Trotter
Publication date: 30 September 2015
Published in: European Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1506.00192
68R10: Graph theory (including graph drawing) in computer science
05C15: Coloring of graphs and hypergraphs
05C85: Graph algorithms (graph-theoretic aspects)
68W27: Online algorithms; streaming algorithms
