Comparing First-Fit and Next-Fit for Online Edge Coloring

Martin R. Ehmsen, Lene M. Favrholdt, Jens S. Kohrt, and Rodica Mihai

19th International Symposium on Algorithms and Computation, to appear

We study the performance of the two well-known edge coloring algorithms First-Fit and Next-Fit using the relative worst-order ratio. Previous analysis using the competitive ratio have not been able to separate their performance. We first consider the min-coloring problem and conclude that First-Fit is better than Next-Fit. Next, we consider the max-coloring problem, and conclude, surprisingly, that First-Fit and Next-Fit are not comparable.