Greedy coloring

Two greedy colorings of the same 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 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 do not in general use the minimum number of colors possible. However, they have been used in mathematics as a technique for proving other results about colorings and in computer science as a heuristic to find colorings with few colors.

Greed is not always good

A crown graph (a complete bipartite graph K_n,n, with the edges of a perfect matching removed) is a particularly bad case for greedy coloring: if the vertex ordering places two vertices consecutively whenever they belong to one of the pairs of the removed matching, then a greedy coloring will use n colors, while the optimal number of colors for this graph is two. 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.^[1] Therefore, it is of some importance in greedy coloring to choose the vertex ordering carefully.

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 forces the greedy algorithm to use k or more colors. In particular, this means that it is difficult to find the worst ordering for G.^[2]

Optimal ordering

The vertices of any graph may always be ordered in such a way that the greedy algorithm produces an optimal coloring. For, given any optimal coloring in which the smallest color set is maximal, the second color set is maximal with respect to the first color set, etc., one may order the vertices by their colors. Then when one uses a greedy algorithm with this order, the resulting coloring is automatically optimal. More strongly, perfectly orderable graphs (which include chordal graphs, comparability graphs, and distance-hereditary graphs) have an ordering that is optimal both for the graph itself and for all of its induced subgraphs.^[3] However, finding an optimal ordering for an arbitrary graph is NP-hard (because it could be used to solve the NP-complete graph coloring problem), and recognizing perfectly orderable graphs is also NP-complete.^[4] For this reason, heuristics have been used that attempt to reduce the number of colors while not guaranteeing an optimal number of colors.

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.^[5] 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.^[6]

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.^[7] However, for interval graphs, a constant competitive ratio is possible,^[8] while for bipartite graphs and sparse graphs a logarithmic ratio can be achieved.^[9] 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.^[9]

Notes

1. Kučera (1991).
2. Zaker (2006).
3. Chvátal (1984).
4. Middendorf & Pfeiffer (1990).
5. Welsh & Powell (1967); Johnson (1979); Sysło (1989); Maffray (2003).
6. Lovász (1975).
7. Lovász, Saks & Trotter (1989); Vishwanathan (1990).
8. Kierstead & Trotter (1981).
9. Irani (1994).

References

• Chvátal, Václav (1984), "Perfectly orderable graphs", in Berge, Claude; Chvátal, Václav, Topics in Perfect Graphs, Annals of Discrete Mathematics 21, Amsterdam: North-Holland, pp. 63–68. As cited by Maffray (2003).
• Irani, Sandy (1994), "Coloring inductive graphs on-line", Algorithmica 11 (1): 53–72, doi:10.1007/BF01294263.
• Kierstead, H. A.; Trotter, W. A. (1981), "An extremal problem in recursive combinatorics", Congressus Numerantium 33: 143–153. As cited by Irani (1994).
• Kučera, Luděk (1991), "The greedy coloring is a bad probabilistic algorithm", Journal of Algorithms 12 (4): 674–684, doi:10.1016/0196-6774(91)90040-6.
• Johnson, D. S. (1979), "Worst case behavior of graph coloring algorithms", Proc. 5th Southeastern Conf. Combinatorics, Graph Theory and Computation, Winnipeg: Utilitas Mathematica, pp. 513–527. As cited by Maffray (2003).
• Lovász, L. (1975), "Three short proofs in graph theory", Journal of Combinatorial Theory, Series B 19 (3): 269–271, doi:10.1016/0095-8956(75)90089-1.
• Lovász, L.; Saks, M. E.; Trotter, W. A. (1989), "An on-line graph coloring algorithm with sublinear performance ratio", Discrete Mathematics 75 (1–3): 319–325, doi:10.1016/0012-365X(89)90096-4.
• Maffray, Frédéric (2003), "On the coloration of perfect graphs", in Reed, Bruce A.; Sales, Cláudia L., Recent Advances in Algorithms and Combinatorics, CMS Books in Mathematics 11, Springer-Verlag, pp. 65–84, doi:10.1007/0-387-22444-0_3, ISBN 0-387-95434-1.
• Middendorf, Matthias; Pfeiffer, Frank (1990), "On the complexity of recognizing perfectly orderable graphs", Discrete Mathematics 80 (3): 327–333, doi:10.1016/0012-365X(90)90251-C.
• Sysło, Maciej M. (1989), "Sequential coloring versus Welsh-Powell bound", Discrete Mathematics 74 (1–2): 241–243, doi:10.1016/0012-365X(89)90212-4.
• Vishwanathan, S. (1990), "Randomized online graph coloring", Proceedings of the 31st IEEE Symposium on Foundations of Computer Science (FOCS '90) 2, pp. 464–469, doi:10.1109/FSCS.1990.89567, ISBN 0-8186-2082-X.
• Welsh, D. J. A.; Powell, M. B. (1967), "An upper bound for the chromatic number of a graph and its application to timetabling problems", The Computer Journal 10 (1): 85–86, doi:10.1093/comjnl/10.1.85.
• Zaker, Manouchehr (2006), "Results on the Grundy chromatic number of graphs", Discrete Mathematics 306 (2–3): 3166–3173, doi:10.1016/j.disc.2005.06.044.