An algorithm to partition a poset into chains is online if the poset is
presented to the algorithm only one element at a time and the algorithm must
assign a chain to the element when it is presented without backtracking.
Kierstead's algorithm to partition any poset of width k requires (5^k-1)/4
chains. The lower bound on this problem due to Szemerdi states that there is no
online algorithm that partitions all posets of width k into fewer than
k(k+1)/2 chains. In this paper, we bridge this enormous gap between the
exponential upper bound and the quadratic lower bound under the condition that
the elements of the poset are presented in a total order consistent with the
poset. We give an online algorithm that requires k(k+1)/2 chains to
partition the poset when its elements are presented in the order of one of its
linear extensions. We also give a lower bound of 2k-1 chains for this problem.