Greedy coloring

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.

The greedy coloring for a given vertex ordering can be computed by an algorithm that runs in linear time.

The time for the overall coloring algorithm is dominated by the calls to this subroutine.

Therefore, the sum of the lengths of the argument lists to first_available, and the total time for the algorithm, are proportional to the number of edges in the graph.

becomes a maximal independent set among the vertices that were not already assigned smaller colors.

For instance, a crown graph (a graph formed from two disjoint sets of n/2 vertices {a1, a2, ...} and {b1, b2, ...} by connecting ai to bj whenever i ≠ j) can be a particularly bad case for greedy coloring.

[5] There also exist graphs such that with high probability a randomly chosen vertex ordering leads to a number of colors much larger than the minimum.

[6] Therefore, it is of some importance in greedy coloring to choose the vertex ordering carefully.

The vertices of any graph may always be ordered in such a way that the greedy algorithm produces an optimal coloring.

Then when one uses a greedy algorithm with this order, the resulting coloring is automatically optimal.

[7] However, because optimal graph coloring is NP-complete, any subproblem that would allow this problem to be solved quickly, including finding an optimal ordering for greedy coloring, is NP-hard.

[8] In interval graphs and chordal graphs, if the vertices are ordered in the reverse of a perfect elimination ordering, then the earlier neighbors of every vertex will form a clique.

It is NP-complete to determine, for a given graph G and number k, whether there exists an ordering of the vertices of G that causes the greedy algorithm to use k or more colors.

[12] They include the cographs, which are exactly the graphs in which all induced subgraphs are well-colored.

[12] If a random graph is drawn from the Erdős–Rényi model with constant probability of including each edge, then any vertex ordering that is chosen independently of the graph edges leads to a coloring whose number of colors is close to twice the optimal value, with high probability.

It remains unknown whether there is any polynomial time method for finding significantly better colorings of these graphs.

[3] Because optimal vertex orderings are hard to find, heuristics have been used that attempt to reduce the number of colors while not guaranteeing an optimal number of colors.

The largest degree of a removed vertex that this algorithm encounters is called the degeneracy of the graph, denoted d. In the context of greedy coloring, the same ordering strategy is also called the smallest last ordering.

For these graphs, the greedy algorithm with the degeneracy ordering is always optimal.

[21] The triangular prism is the smallest graph for which one of its degeneracy orderings leads to a non-optimal coloring, and the square antiprism is the smallest graph that cannot be optimally colored using any of its degeneracy orderings.

By keeping track of the sets of neighboring colors and their cardinalities at each step, it is possible to implement this method in linear time.

Alternative color selection strategies have been studied within the framework of online algorithms.

[26] If no additional restrictions on the graph are given, the optimal competitive ratio is only slightly sublinear.

One of the early applications of the greedy algorithm was to problems such as course scheduling, in which a collection of tasks must be assigned to a given set of time slots, avoiding incompatible tasks being assigned to the same time slot.

[31] In combinatorial game theory, for an impartial game given in explicit form as a directed acyclic graph whose vertices represent game positions and whose edges represent valid moves from one position to another, the greedy coloring algorithm (using the reverse of a topological ordering of the graph) calculates the nim-value of each position.

Brooks' theorem states that with two exceptions (cliques and odd cycles) at most Δ colors are needed.