Randomized online graph coloring

4 December 2002

conference paper
Published by Institute of Electrical and Electronics Engineers (IEEE)

p. 464-469vol.2
https://doi.org/10.1109/fscs.1990.89567

Abstract

It is shown that randomization helps in coloring graphs online, and a simple randomized online algorithm is presented. For 3-colorable graphs the expected number of colors the algorithm uses is O((n log n)/sup 1/2/). The algorithm runs in polynomial time and compares well with the best known polynomial-time offline algorithms. A lower bound is proved for the randomized algorithm.

Keywords

RANDOMIZED ONLINE GRAPH COLORING
COLORING GRAPHS ONLINE
RANDOMIZED ALGORITHM
EXPECTED NUMBER
ALGORITHM USE
POLYNOMIAL TIME
N LOG N
3-COLORABLE GRAPH
SIMPLE RANDOMIZED ONLINE ALGORITHM
POLYNOMIAL-TIME OFFLINE ALGORITHM
POLYNOMIALS
COMPUTER SCIENCE
UPPER BOUND
LOWER BOUND
ONLINE ALGORITHM
GRAPH COLORING
TREE GRAPHS

This publication has 3 references indexed in Scilit:

An on-line graph coloring algorithm with sublinear performance ratio
Discrete Mathematics, 1989
Probabilistic computations: Toward a unified measure of complexity
Published by Institute of Electrical and Electronics Engineers (IEEE) ,1977
Effective coloration
The Journal of Symbolic Logic, 1976