Forbidden structures for efficient First-Fit chain partitioning (extended abstract)

Using natural numbers for identifying chains, First-Fit algorithm processes elements of a poset P in some order and for each element it assigns the smallest natural number such that all elements with the same number form a chain. class P of posets with bounded-width we prove that there is a constant c such that all posets from P are partitioned by First-Fit into at most c chains if and only if there is a width 2 poset not induced by any poset from P .