Greedy Coloring - Heuristic Ordering Strategies

Heuristic Ordering Strategies

A commonly used ordering for greedy coloring is to choose a vertex v of minimum degree, order the remaining vertices, and then place v last in the ordering. If every subgraph of a graph G contains a vertex of degree at most d, then the greedy coloring for this ordering will use at most d + 1 colors. The smallest such d is commonly known as the degeneracy of the graph.

For a graph of maximum degree Δ, any greedy coloring will use at most Δ + 1 colors. Brooks' theorem states that with two exceptions (cliques and odd cycles) at most Δ colors are needed. One proof of Brooks' theorem involves finding a vertex ordering in which the first two vertices are adjacent to the final vertex but not adjacent to each other, and each subsequent vertex has at least one earlier neighbor. For an ordering with this property, the greedy coloring algorithm uses at most Δ colors.