Greedy Coloring by Vertex Order

The Greedy Rule for a Fixed Order

A vertex-coloring procedure needs a rule for deciding what to do next. In greedy coloring, we first choose an order of the vertices, then process them one by one. Each vertex receives the smallest positive integer that has not already been assigned to any of its previously colored neighbors. The rule is simple, but the result is determined by the local information available at each step: unprocessed neighbors do not yet restrict the current choice.

Throughout, graphs are finite and simple. A proper vertex coloring assigns colors to vertices so that the endpoints of every edge have different colors. We represent colors by positive integers \(1,2,3,\ldots\); the integers are labels, not quantities to be compared in any way other than their order. A vertex order of a graph with \(n\) vertices is a list \(v_1,v_2,\ldots,v_n\) in which every vertex occurs exactly once.

More formally, let \(c(v_j)\) denote the color assigned at step \(j\). The colors forbidden at step \(i\) form the set

The algorithm assigns \(c(v_i)=\min(\{1,2,3,\ldots\}\setminus F_i)\). This least color always exists: \(F_i\) is finite, since it comes from at most \(i-1\) vertices, while the positive integers form an infinite set. The choice is based only on neighbors that have already been processed. After the last step, the output is a coloring of all vertices.

Why the Procedure Produces a Proper Coloring

Proof. At each step \(i\), the set \(F_i\) is finite, so the least positive integer outside it exists and the algorithm can assign a color. There are \(n\) vertices, and each is processed once; therefore the algorithm terminates after \(n\) steps. To check that its output is proper, take any edge \(v_iv_j\), and suppose \(i<j\). When \(v_j\) is processed, \(v_i\) is already colored and is a neighbor, so \(c(v_i)\in F_j\). The algorithm chooses \(c(v_j)\) outside \(F_j\), which gives \(c(v_j)\ne c(v_i)\). This holds for every edge, so the completed coloring is proper. \(\square\)

This argument also explains why the order matters to the calculation: when a vertex is reached, the algorithm consults its earlier neighbors, not every neighbor indiscriminately. A later neighbor cannot forbid a color at the current step, because it has not been colored yet. If \(V\) is empty, there are no steps and the empty assignment is proper, since there are no edges to check.

Proof. Let \(q\) be the largest color assigned, and consider the step at which color \(q\) is assigned. Since the algorithm chooses the least available color, each positive integer \(k<q\) must be forbidden at that step. Thus, for each such \(k\), some already colored neighbor has color \(k\), so the algorithm has used \(k\). It has also used \(q\) at the step under consideration. No color larger than \(q\) is used by the definition of \(q\), so the set of colors used is exactly \(\{1,2,\ldots,q\}\). \(\square\)

Tracing the Algorithm

A careful trace records four things at each step: the vertex being processed, its already colored neighbors, the colors those neighbors forbid, and the color assigned. The examples below specify each graph by its vertex and edge sets, so the adjacency information does not depend on a drawing. In each table, a dash means that the vertex has no already colored neighbors.

Common Mistake: Looking at Only Some Earlier Neighbors

In the disconnected-graph example, vertex 3 was processed last. A mistaken trace might inspect only its neighbor 1, notice color 1, and assign color 2. But vertex 2 is also a neighbor of 3 and already has color 2. This incorrect assignment would make edge \(23\) have color 2 at both endpoints. The correction is to list all already colored neighbors before choosing: vertex 1 forbids 1 and vertex 2 forbids 2, so vertex 3 must receive 3.

Another potential confusion is to treat every neighbor as a restriction at every step. Only already colored neighbors belong in the forbidden set. For instance, when vertex \(a\) is processed in the third example, \(c\) is a neighbor but has not yet been processed. It therefore does not forbid a color at that step. The algorithm will account for the edge \(ac\) when \(c\) is processed, as the proper-coloring proof guarantees.

Using and Checking a Greedy Coloring

The procedure is useful whenever a coloring must be constructed directly from local information. It can be carried out from an edge list: maintain the colors already assigned, inspect the earlier neighbors of the next vertex, and select the first positive integer missing from their colors. The output is a valid coloring regardless of the order, because the theorem applies to every specified order. The number of colors used is a separate feature of the particular output; the proof of validity does not claim that this number is the chromatic number.

For a small graph, a reliable hand calculation can follow this checklist:

• Write the complete vertex order before assigning any colors.
• At each step, identify all neighbors that occur earlier in that order.
• Form the set of their assigned colors, removing duplicates if several neighbors share a color.
• Choose the least positive integer outside that set.
• At the end, check every edge against the two endpoint colors.

The last check is valuable even when the procedure has been followed carefully: it can expose a missed neighbor or a copied color from the wrong step. A coloring is proper precisely when every edge has differently colored endpoints; checking only some edges is not enough.