On-Line Edge-Coloring with a Fixed Number of Colors

Lene Monrad Favrholdt, Morten Nyhave Nielsen

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


We investigate a variant of on-line edge-coloring in which there is a fixed number of colors available and the aim is to color as many edges as possible. We prove upper and lower bounds on the performance of different classes of algorithms for the problem. Moreover, we determine the performance of two specific algorithms, First-Fit and Next-Fit. Specifically, algorithms that never reject edges that they are able to color are called fair algorithms. We consider the four combinations of fair/not fair and deterministic/randomized. We show that the competitive ratio of deterministic fair algorithms can vary only between approximately 0.4641 and 1/2, and that Next-Fit is worst possible among fair algorithms. Moreover, we show that no algorithm is better than 4/7-competitive. If the graphs are all k-colorable, any fair algorithm is at least 1/2-competitive. Again, this performance is matched by Next-Fit while the competitive ratio for First-Fit is shown to be k/(2k - 1), which is significantly better, as long as k is not too large.
Translated title of the contributionEn
Original languageEnglish
Title of host publicationFoundations of Software Technology and Theoretical Computer Science
Number of pages11
Publication date2000
Publication statusPublished - 2000
EventFoundations of Software Technology and Theoretical Computer Science -
Duration: 24. Aug 2010 → …


ConferenceFoundations of Software Technology and Theoretical Computer Science
Period24/08/2010 → …


Dive into the research topics of 'On-Line Edge-Coloring with a Fixed Number of Colors'. Together they form a unique fingerprint.

Cite this