First-Fit Algorithm for the On-Line Chain Partitioning Problem
Bartłomiej Bosek, Tomasz Krawczyk, Edward Szczypka · SIAM Journal on Discrete Mathematics · 2010
We consider a problem of partitioning a partially ordered set into chains by first-fit algorithm. In general this algorithm uses arbitrarily many chains on a class of bounded width posets. In this paper we prove that First-Fit uses at most $3tw^2$ chains to partition any poset of width w which does not induce two incomparable chains of height t. In this way we get a wide class of posets with polynomial bound for the on-line chain partitioning problem. We also discuss some consequences of our result for coloring graphs by First-Fit.