First-Fit Algorithm for the On-Line Chain Partitioning Problem

Abstract

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.