Randomized online graph coloring
S Vishwanathan - Journal of algorithms, 1992 - Elsevier
We study the problem of coloring graphs in an online manner. The only known deterministic
online graph coloring algorithm with a sublinear performance function was found by Lovász,
Saks, and Trotter,(Discrete Math. 75 (1989), 319–325). Their algorithm colors graphs of
chromatic number χ with no more than (2χn) log∗ n colors, where n is the number of
vertices. They point out that the performance can be improved slightly for graphs with
bounded chromatic number. For three-chromatic graphs the number of colors used, for …
online graph coloring algorithm with a sublinear performance function was found by Lovász,
Saks, and Trotter,(Discrete Math. 75 (1989), 319–325). Their algorithm colors graphs of
chromatic number χ with no more than (2χn) log∗ n colors, where n is the number of
vertices. They point out that the performance can be improved slightly for graphs with
bounded chromatic number. For three-chromatic graphs the number of colors used, for …