Two greedy colorings of the same crown graph using different vertex orders. The right example generalises to 2-colorable graphs with n vertices, where the greedy algorithm expends n/2 colors.
In the study of graph coloring problems in mathematics and computer science, a greedy coloring or sequential coloring[1] is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence and assigns each vertex its first available color. Greedy colorings can be found in linear time, but they do not, in general, use the minimum number of colors possible.
Different choices of the sequence of vertices will typically produce different colorings of the given graph, so much of the study of greedy colorings has concerned how to find a good ordering. There always exists an ordering that produces an optimal coloring, but although such orderings can be found for many special classes of graphs, they are hard to find in general. Commonly used strategies for vertex ordering involve placing higher-degree vertices earlier than lower-degree vertices, or choosing vertices with fewer available colors in preference to vertices that are less constrained.
Variations of greedy coloring choose the colors in an online manner, without any knowledge of the structure of the uncolored part of the graph, or choose other colors than the first available in order to reduce the total number of colors. Greedy coloring algorithms have been applied to scheduling and register allocation problems, the analysis of combinatorial games, and the proofs of other mathematical results including Brooks' theorem on the relation between coloring and degree.
Other concepts in graph theory derived from greedy colorings include the Grundy number of a graph (the largest number of colors that can be found by a greedy coloring), and the well-colored graphs, graphs for which all greedy colorings use the same number of colors.
the study of graph coloring problems in mathematics and computer science, a greedycoloring or sequential coloring is a coloring of the vertices of a...
quality of the resulting coloring depends on the chosen ordering. There exists an ordering that leads to a greedycoloring with the optimal number of...
best overall solution later. For example, all known greedycoloring algorithms for the graph coloring problem and all other NP-complete problems do not...
undirected graph is the maximum number of colors that can be used by a greedycoloring strategy that considers the vertices of the graph in sequence and assigns...
include both types of edges. greedy Produced by a greedy algorithm. For instance, a greedycoloring of a graph is a coloring produced by considering the...
set of vertices with a given color must form an independent set. A greedycoloring gives the upper bound χ ( G ) ≤ Δ ( G ) + 1 {\displaystyle \chi (G)\leq...
Chordal graphs are perfectly orderable: an optimal coloring may be obtained by applying a greedycoloring algorithm to the vertices in the reverse of a perfect...
edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem...
maximum degree Δ are O(Δ⌊k/2⌋), where the degeneracy bound shows that a greedycoloring algorithm may be used to color the graph with this many colors. For...
Chvátal's art gallery theorem by Fisk (1978). A 3-coloring may be found in linear time by a greedycoloring algorithm that removes any vertex of degree at...
degeneracy, the graphs with Hadwiger number at most k can be colored by a greedycoloring algorithm using O ( k log k ) {\displaystyle O(k{\sqrt {\log k}})}...
(sequence A094047 in the OEIS) Crown graphs can be used to show that greedycoloring algorithms behave badly in the worst case: if the vertices of a crown...
registers representing available colors) would be a coloring for the original graph. As Graph Coloring is an NP-Hard problem and Register Allocation is in...
upper bound, proved in Heawood's original short paper, is based on a greedycoloring algorithm. By manipulating the Euler characteristic, one can show that...
incremental construction sequence using a greedycoloring algorithm, the result will be an optimal coloring. The reverse of the vertex ordering used in...
few resources as possible; it can be found in polynomial time by a greedycoloring algorithm that colors the intervals in sorted order by their left endpoints...
graph is a graph whose vertices can be ordered in such a way that a greedycoloring algorithm with that ordering optimally colors every induced subgraph...
graphs are perfectly orderable graphs, a subclass of perfect graphs: a greedycoloring algorithm for a topological ordering of a transitive orientation of...
cograph is a hereditarily well-colored graph, a graph such that every greedycoloring of every induced subgraph uses an optimal number of colors. A graph...
Global Information