Alternative Color Selection Schemes
It is possible to define a greedy coloring algorithm in which the vertices of the given graph are colored in a given sequence but in which the color chosen for each vertex is not necessarily the first available color; alternative color selection strategies have been studied within the framework of online algorithms. In the online graph-coloring problem, vertices of a graph are presented one at a time in an arbitrary order to a coloring algorithm; the algorithm must choose a color for each vertex, based only on the colors of and adjacencies among already-processed vertices. In this context, one measures the quality of a color selection strategy by its competitive ratio, the ratio between the number of colors it uses and the optimal number of colors for the given graph.
If no additional restrictions on the graph are given, the optimal competitive ratio is only slightly sublinear. However, for interval graphs, a constant competitive ratio is possible, while for bipartite graphs and sparse graphs a logarithmic ratio can be achieved. Indeed, for sparse graphs, the standard greedy coloring strategy of choosing the first available color achieves this competitive ratio, and it is possible to prove a matching lower bound on the competitive ratio of any online coloring algorithm.
Read more about this topic: Greedy Coloring
Famous quotes containing the words alternative, color, selection and/or schemes:
“It is a secret from nobody that the famous random event is most likely to arise from those parts of the world where the old adage “There is no alternative to victory” retains a high degree of plausibility.”
—Hannah Arendt (1906–1975)
“He could jazz up the map-reading class by having a full-size color photograph of Betty Grable in a bathing suit, with a co- ordinate grid system laid over it. The instructor could point to different parts of her and say, “Give me the co-ordinates.”... The Major could see every unit in the Army using his idea.... Hot dog!”
—Norman Mailer (b. 1923)
“The books for young people say a great deal about the selection of Friends; it is because they really have nothing to say about Friends. They mean associates and confidants merely.”
—Henry David Thoreau (1817–1862)
“Science is a dynamic undertaking directed to lowering the degree of the empiricism involved in solving problems; or, if you prefer, science is a process of fabricating a web of interconnected concepts and conceptual schemes arising from experiments and observations and fruitful of further experiments and observations.”
—James Conant (1893–1978)