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

Lene Monrad Favrholdt, Morten Nyhave Nielsen

Research output: Contribution to journalJournal articleResearchpeer-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.
Original languageEnglish
Issue number2
Pages (from-to)176-191
Publication statusPublished - 2003


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

Cite this