On first-fit coloring of ladder-free posets

Bosek and Krawczyk exhibited an on-line algorithm for partitioning an on-line poset of width ww into w14lgww14lgw chains. They also observed that the problem of on-line chain partitioning of general posets of width ww could be reduced to First-Fit chain partitioning of 2w2+12w2+1-ladder-free posets of width ww, where an mm-ladder is the transitive closure of the union of two incomparable chains x1≤⋯≤xmx1≤⋯≤xm, y1≤⋯≤ymy1≤⋯≤ym and the set of comparabilities {x1≤y1,…,xm≤ym}{x1≤y1,…,xm≤ym}. Here, we provide a subexponential upper bound (in terms of ww with mm fixed) for the performance of First-Fit chain partitioning on mm-ladder-free posets, as well as an exact quadratic bound when m=2m=2, and an upper bound linear in mm when w=2w=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.