On first-fit coloring of ladder-free posets

Bosek and Krawczyk exhibited an on-line algorithm for partitioning an on-line poset of width w into w 14 lg w chains. They also observed that the problem of on-line chain partitioning of general posets of width w could be reduced to First-Fit chain partitioning of 2 w 2 + 1 -ladder-free posets of width w , where an m -ladder is the transitive closure of the union of two incomparable chains x 1 ≤ ⋯ ≤ x m , y 1 ≤ ⋯ ≤ y m and the set of comparabilities { x 1 ≤ y 1 , … , x m ≤ y m } . Here, we provide a subexponential upper bound (in terms of w with m fixed) for the performance of First-Fit chain partitioning on m -ladder-free posets, as well as an exact quadratic bound when m = 2 , and an upper bound linear in m when w = 2 . Using the Bosek–Krawczyk observation, this yields an on-line chain partitioning algorithm with a somewhat improved performance bound. More importantly, the algorithm and the proof of its performance bound are much simpler.