$title = "Research"; $name = "Lene Monrad Favrholdt"; $login = "lenem"; include("/home/www/Employees/svalle/PHP/template.php3"); ?>
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.