Why do greedy coloring algorithms mess up?

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?

• I think you might be asking a bit much. It's surprising to almost everybody that graph coloring can't be done in a greedy way. One slightly higher brow way to "explain" this is to say that graph coloring isn't a local property, in the informal sense that how you color parts of a graph that are "far away" can have impacts on how you're allowed to color a graph "nearby". In fact, I think this is really the foundational notion. Instead of asking why graph coloring isn't local, you should instead show that other problems aren't local by comparing them to graph coloring. May 13 at 21:24
• That makes sense and is along the lines of what I'm seeking here! What is an example of a local property, in that case? And while it certainly seems like it, is it the case that such "local properties" are generally determinable in a greedy way? May 13 at 22:48
• In the context of coloring, there's a natural example of a simple local bound and a simple non-local bound. Locally, we have $\chi(G) \ge \omega(G)$, the clique number: any $k$-vertex clique by itself needs at least $k$ colors. Non-locally, we have $\chi(G) \ge n/\alpha(G)$, where $\alpha(G)$ is the independence number: we need this many colors because each color can be used at most $n/\alpha(G)$ times. May 14 at 0:12

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$$).

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.

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.

• Thank you for your answer. However, it seems tangentially related to my question, which was not about how we can get GCA to optimally work, but more about why it fails to do so. Nonetheless, I wanted to ask (a) how lowest degree last differs from highest degree first (since it seems as if the difference matters sufficiently for you to list them as two different heuristics) (b) how does one decide which heuristic to use when? For example, planar graphs seem to be better suited to lowest degree first, but what if you're given a graph without necessarily nice properties, say? May 13 at 22:37
• Lowest degree last is also an "adaptive" degree method to some extent: once you've determined which vertex $v$ goes last, the vertex that comes right before it is determined by the degrees of $G-v$, not the degrees of $G$. When this method is finished, the end of the list will be approximately the same as for highest degree first, but the beginnings of the two lists will not have any relation to each other. May 13 at 22:41
• There's a lot of research about which heuristic to use: see this paper for an example. You're going to be using greedy coloring on very large graphs you can't color more intelligently, so a big factor is "how fast is the algorithm implementing the heuristic"? Possibly you just implement the most expensive strategy you can get away with, because these heuristics wouldn't have stuck around if they were slower and worse. May 13 at 22:45