  We study a version of online edge coloring, where the goal is to color as
many edges as possible using only a given number, $k$, of available colors. All
of our results are with regard to competitive analysis. Previous attempts to
identify optimal algorithms for this problem have failed, even for bipartite
graphs. Thus, in this paper, we analyze even more restricted graph classes,
paths and trees. For paths, we consider $k=2$, and for trees, we consider any
$k \geq 2$.
  We prove that a natural greedy algorithm called First-Fit is optimal among
deterministic algorithms, on paths as well as trees. For paths, we give a
randomized algorithm, which is optimal and better than the best possible
deterministic algorithm. For trees, we prove that to obtain a better
competitive ratio than First-Fit, the algorithm would have to be both
randomized and unfair (i.e., reject edges that could have been colored), and
even such algorithms cannot be much better than First-Fit.
