Why Greedy Coloring Depends on Vertex Order

Why the Order Matters

A greedy coloring makes a local decision at each step: give the next vertex the smallest color not already used by its colored neighbors. The rule is simple, but its result can depend on which vertex comes next. A vertex may receive a color because of an earlier neighbor that would not have been colored yet in a different order. Later vertices must work with the choices already made; the algorithm does not go back and revise them.

We consider finite simple graphs. A proper vertex coloring assigns colors to vertices so that adjacent vertices receive different colors. The chromatic number \(\chi(G)\) is the smallest number of colors in any proper coloring of \(G\). A vertex order is a list containing every vertex exactly once. To compare orders fairly, we use the same rule each time and change only the list.

Only already-colored neighbors restrict the choice at a step. A neighbor appearing later in the order has no effect yet. This is the key distinction between greedy coloring and a search that can revise earlier decisions: greedy coloring commits to each first available color immediately.

What the Rule Guarantees

Proof. Consider any edge \(uv\), and suppose \(u\) appears before \(v\). When the algorithm colors \(v\), the vertex \(u\) has already been colored. The rule assigns \(v\) a color different from the color of every already-colored neighbor, including \(u\). Thus the endpoints of every edge receive different colors, which is exactly the definition of a proper coloring. If the graph has no edges, the condition is vacuous, so the conclusion also holds. \(\square\)

This guarantee concerns validity, not optimality. A proper coloring may use more colors than necessary. In particular, the fact that the algorithm always chooses the smallest available color does not mean it uses the smallest possible total number of colors: its earlier choices can affect later vertices.

How an Early Choice Can Force an Extra Color

In the second order above, vertices 1 and 4 are not adjacent, so both can be assigned color 1. Vertex 2 is adjacent to 1 but not 4, so it receives color 2. The final vertex, 3, is adjacent to both 2 and 4. Those two neighbors have different colors, leaving neither color 1 nor color 2 available. The extra color is forced by the combination of earlier choices around vertex 3, not by the graph needing three colors globally.

This also explains why inspecting the final coloring alone is not enough to understand the algorithm. To check a greedy calculation, reconstruct each step in the stated order and check exactly which earlier neighbors constrain the choice. Later neighbors do not block a color when a vertex is processed, though properness will still be ensured when those later vertices are colored.

An Order That Attains the Chromatic Number

Order dependence does not mean that greedy coloring must be wasteful on every order. In fact, for every nonempty finite graph there is an order for which the greedy algorithm uses exactly \(\chi(G)\) colors. The existence argument gives a useful contrast: greedy coloring can be far from optimal on one order, but a suitable order can make it optimal.

Proof. Write \(k=\chi(G)\), and choose a proper coloring with \(k\) colors. Such a coloring exists by the definition of \(\chi(G)\); because \(G\) is finite, assigning a different color to every vertex gives at least one proper coloring, so the set of possible color counts has a minimum. Let its nonempty color classes be \(C_1,\dots,C_k\), with the classes listed in any order, and order the vertices by listing all of \(C_1\), then all of \(C_2\), and so on through \(C_k\). We show inductively that vertices in \(C_i\) receive only colors from \(\{1,\dots,i\}\). For \(C_1\), its vertices are pairwise nonadjacent, so each has no earlier neighbor in \(C_1\) and receives color 1. Now suppose every vertex in \(C_1\cup\cdots\cup C_{i-1}\) has color at most \(i-1\). A vertex in \(C_i\) has no neighbor earlier in \(C_i\), because \(C_i\) is an independent set. Its earlier neighbors are therefore in earlier classes and have colors at most \(i-1\). Color \(i\) is available, so the greedy rule assigns a color at most \(i\). This proves the claim for every class. The resulting greedy coloring uses at most \(k\) colors, and it is proper by the preceding theorem. Since \(k=\chi(G)\), no proper coloring can use fewer than \(k\) colors. Thus this order uses exactly \(k\) colors. \(\square\)

The argument does not say that every order grouped by an arbitrary collection of color classes will work. The classes used in the proof must come from an optimal coloring, and the proof’s ordering puts each entire class before the next. Even with an optimal coloring in hand, a different order can make earlier greedy choices introduce colors that are unnecessary globally.

A Common Mistake

Wrong calculation: In the \(P_4\) example with order \(1,4,2,3\), one might say that vertex 3 gets color 1 because it is not adjacent to vertex 1, or color 2 because its most recently processed neighbor, vertex 2, has color 2. Neither calculation applies the rule: vertex 3 is adjacent to both 2 and 4, and both are already colored.

Correction: At the step for vertex 3, its earlier neighbors are 2 and 4. Their colors are 2 and 1, respectively. Thus color 1 is forbidden by neighbor 4, color 2 is forbidden by neighbor 2, and the smallest available color is 3. Check every earlier neighbor, not only the immediately preceding vertex or one neighbor selected for inspection.

When using a greedy coloring, keep the order visible and record the colors on the current vertex’s earlier neighbors before assigning its color. Then check the final result edge by edge. This separates two questions: whether the output is a proper coloring, and whether it uses the minimum possible number of colors.