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: | Lovsz Lszl, Saks Michael, Trotter W.T. |
Keywords: | combinatorial analysis |
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