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:
“Education must, then, be not only a transmission of culture but also a provider of alternative views of the world and a strengthener of the will to explore them.”
—Jerome S. Bruner (20th century)
“The intellect,—that is miraculous! Who has it, has the talisman: his skin and bones, though they were of the color of night, are transparent, and the everlasting stars shine through, with attractive beams.”
—Ralph Waldo Emerson (1803–1882)
“It is the highest and most legitimate pride of an Englishman to have the letters M.P. written after his name. No selection from the alphabet, no doctorship, no fellowship, be it of ever so learned or royal a society, no knightship,—not though it be of the Garter,—confers so fair an honour.”
—Anthony Trollope (1815–1882)
“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)