Why do greedy coloring algorithms mess up?

Question

It is a well-known fact that, for a graph, the greedy coloring algorithm does not always return the most optimal coloring. That is, it strongly depends on the ordering of the vertices as they are colored. I was trying to understand what exactly about a particular vertex ordering makes the GCA mess up. Please feel free to share your intuitions - that is more of what I am seeking, rather than rigorous details.

For example, why is it (usually) better to place higher-degree vertices earlier in the ordering?

Answer 1

I like @HallaSurvivor's intuition that coloring isn't a local property. From an Algorithms perspective, there are two properties to consider for when the greedy algorithm works.

The first property is called optimal substructure. Effectively, a problem has the optimal substructure property if an optimal solution to a given problem restricts to optimal solutions on sub-problems. In the case of graph coloring, does an optimal coloring of the graph $G$ restrict to an optimal coloring of its subgraphs? The answer is no. Start with the Wheel graph $W_{n+1}$ (we have a cycle graph $C_{n}$ with a vertex $v_{n+1}$ adjacent to each vertex on the cycle). Now remove all edges on the cycle, so we have a $K_{1,n}$ left. An optimal coloring of the wheel does not restrict to an optimal coloring of the $K_{1,n}$.

The other property is the greedy exchange property (think linear independence, trees, and matroids). Can we exchange one or more colors to get a coloring that is at least as good as our current coloring? In general, it is not clear that we can do so.

Graphs where the local colorings extend to global colorings are called perfect graphs. Precisely, we say that a graph $G$ is perfect if for every $S \subseteq V(G)$, $\chi(G[S]) = \omega(G[S])$ (where $G[S]$ is the subgraph induced by $S$).

Answer 2

The first thing to note is that everything depends on the heuristic you use to order the vertices. On the one hand, if you knew an optimal coloring, you could get the greedy algorithm to produce it: just feed it all the vertices of one color, then all the vertices of another color, and so on. On the other hand, all known simple heuristics fail on some counterexamples.

Here are a few popular heuristics and their justifications.

Highest degree first

We are forced to use a new color when we get to a vertex and all previously used colors already appear on its neighbors. This is most likely to happen with high-degree vertices: if many of their neighbors have already been colored when you get to them, then you're likely to be forced to use a new color. So this heuristic goes through vertices from highest to lowest degree, to catch the high-degree vertices before many of their neighbors have been colored.

Adaptive degree counts

We can try to improve on the reasoning above. High-degree vertices are not a threat to start with: high-degree vertices gradually become more and more threatening as you color more and more neighbors. So we can take that threat measure into account instead, as we go:

• The incidence degree heuristic says that at each step, we color the vertex which has the most already-colored neighbors.
• The saturation degree heuristic says that at each step, we color the vertex with the largest number of distinct colors represented among its neighbors.

Lowest degree last

This is a trickier one which plans out the entire ordering in advance. Starting with an $n$-vertex graph $G$, we pick a vertex $v$ with the lowest degree, and put that one last. Then recursively apply this algorithm to $G-v$ to order the $n-1$ vertices that will come before $v$.

Part of the justification is the same: towards the end of the algorithm, when many vertices have been colored, we don't want to get stuck with a high-degree vertex such that all the different colors appear on its neighbors, because that's what will force you to use an extra color.

The other part of the justification for this heuristic is its guaranteed performance on some classes of graphs. For example, the lowest degree in a planar graph is guaranteed to be $5$ or less, and so this heuristic is guaranteed to color any planar graph with $6$ colors. More generally, it colors any $k$-degenerate graph with $k+1$ colors.