FIRST-FIT ALGORITHM FOR THE ON-LINE CHAIN PARTITIONING PROBLEM.

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² 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. [ABSTRACT FROM AUTHOR]