Comparing First-Fit and Next-Fit for online edge coloring

We study the performance of the algorithms First −Fit and Next −Fit for two online edge coloring problems. In the min-coloring problem, all edges must be colored using as few colors as possible. In the max-coloring problem, a fixed number of colors is given, and as many edges as possible should be colored. Previous analysis using the competitive ratio has not separated the performance of First −Fit and Next −Fit, but intuition suggests that First −Fit should be better than Next −Fit. We compare First −Fit and Next −Fit using the relative worst-order ratio, and show that First −Fit is better than Next −Fit for the min-coloring problem. For the max-coloring problem, we show that First −Fit and Next −Fit are not strictly comparable, i.e., there are graphs for which First −Fit is significantly better than Next −Fit and graphs where Next −Fit is slightly better than First −Fit.