An on-line graph coloring algorithm with sublinear performance ratio

An on-line graph coloring algorithm with sublinear performance ratio

0.00 Avg rating0 Votes
Article ID: iaor19881174
Country: Netherlands
Volume: 43
Start Page Number: 319
End Page Number: 325
Publication Date: May 1989
Journal: Annals of Discrete Mathematics
Authors: , ,
Keywords: combinatorial analysis
Abstract:

One of the simplest heuristics for obtaining a proper coloring of a graph is the First-Fit algorithm: Fix an arbitrary ordering of the vertices and, using the positive integers as the color set, assign to each successive vertex the least integer possible (keeping the coloring proper). This is an example of an on-line algorithm for graph coloring. In the on-line model, a graph is presented one vertex at a time. Each new vertex is given together with all edges joining it to previous vertices. An on-line coloring algorithm assigns a color to each vertex as it is received and once assigned, the color cannot be changed. The performance function, ρÅ(n), of an on-line algorithm is the maximum over all graphs G on n vertices of the ratio of the number of colors used by to color G to the chromatic numbers of G. The First-Fit algorithm has performance function n/4. We exhibit an algorithm with sublinear performance function.

Reviews

Required fields are marked *. Your email address will not be published.