First-Fit Coloring of Incomparability Graphs
Bartłomiej Bosek, Tomasz Krawczyk, Grzegorz Matecki · SIAM Journal on Discrete Mathematics · 2013
One of the simplest heuristics for obtaining a proper coloring of a graph is the first-fit algorithm. First-fit visits each vertex of the graph in the specified order and assigns to every point the least possible number. Let $\mathcal{G}$ be a class of incomparability graphs with bounded maximum clique size, closed under taking induced subgraphs. We prove that first-fit uses a bounded number of colors on the graphs in $\mathcal{G}$ iff there is an incomparability graph of clique size $2$ not contained in $\mathcal{G}$.