Carrying Out Greedy Coloring
Greedy coloring turns a specified vertex order into a coloring by making one local choice at a time. At each step, the current vertex receives the smallest positive-integer color not used by any of its already colored neighbors. The calculation is simple, but it is important to inspect all previously colored neighbors of the current vertex: a color used elsewhere in the graph does not matter unless a neighbor uses it.
All graphs in this tutorial are finite and simple. A proper vertex coloring assigns colors to vertices so that the endpoints of every edge receive different colors. The chromatic number \(\chi(G)\) is the least number of colors in any proper coloring of \(G\). A greedy coloring is one particular coloring, constructed using a specified order; its color count need not by itself establish \(\chi(G)\).
For a step-by-step record, list the previously colored neighbors, their colors, the set of forbidden colors, and the least available color chosen. The forbidden set is formed only from the colored neighbors’ colors. For instance, a color already used on a vertex that is not adjacent to the current vertex remains available.
Why the Rule Gives a Proper Coloring
Proof. The procedure reaches each vertex once, and at each step at most \(n-1\) colors have been used on its previously colored neighbors. Therefore at least one positive integer is available: among the \(n\) colors \(1,\dots,n\), at most \(n-1\) are forbidden. The least available color is consequently defined. To check propriety, consider any edge \(v_iv_j\), with \(i<j\). When \(v_j\) is colored, \(v_i\) is already colored, and \(v_i\) is a neighbor of \(v_j\). The rule forbids the color of \(v_i\), so \(v_j\) receives a different color. This holds for every edge, proving that the final coloring is proper. If \(V\) is empty, the procedure assigns no colors and there are no edges to violate propriety, so the statement also holds in that case. \(\square\)
Proof. The greedy rule gives \(v_i\) the least available positive integer. If its color is \(k\), every smaller positive integer was unavailable at that step. A color is unavailable only if it appears on a previously colored neighbor, so every color from \(1\) through \(k-1\) appears on such a neighbor. In particular, whenever color \(k\) is used, every smaller color has already appeared. Thus the set of labels used has no gaps: it is \(1,2,\dots,r\) for its largest label \(r\). Its size is \(r\), as claimed. If no vertices are present, the set of labels is empty and the number used is zero. \(\square\)
The proposition is useful when reading a completed trace: the largest color label is also the total number of colors used. The theorem guarantees a proper coloring, but it does not claim that the resulting color count is the smallest possible. The examples below focus on the actual output of the specified procedure and verify it directly.
Worked Traces on Edge-Listed Graphs
Worked Example: A Triangle with Two Additional Edges
Let \(G=(V,E)\) have \(V=\{a,b,c,d,e\}\) and \(E=\{ab,ac,bc,bd,cd,de\}\). Use the order \(a,b,c,d,e\). At each row, “available” means the positive integers not in the forbidden set; the chosen color is the least one.
| Vertex | Previously colored neighbors and colors | Forbidden colors | Available colors and choice |
|---|---|---|---|
| \(a\) | None | \(\varnothing\) | \(1,2,\dots\); choose \(1\) |
| \(b\) | \(a:1\) | \(\{1\}\) | \(2,3,\dots\); choose \(2\) |
| \(c\) | \(a:1,\ b:2\) | \(\{1,2\}\) | \(3,4,\dots\); choose \(3\) |
| \(d\) | \(b:2,\ c:3\) | \(\{2,3\}\) | \(1,4,5,\dots\); choose \(1\) |
| \(e\) | \(d:1\) | \(\{1\}\) | \(2,3,\dots\); choose \(2\) |
The final color classes are \(\{a,d\}\), \(\{b,e\}\), and \(\{c\}\). To check the coloring, inspect each listed edge: \(ab\) has colors \(1,2\); \(ac\) has \(1,3\); \(bc\) has \(2,3\); \(bd\) has \(2,1\); \(cd\) has \(3,1\); and \(de\) has \(1,2\). Each edge has differently colored endpoints, so the coloring is proper. Its labels are \(1,2,3\), hence it uses three colors. Also, \(a,b,c\) form a triangle, so any proper coloring needs at least three colors. Therefore this example’s coloring uses exactly \(\chi(G)=3\).
Worked Example: A Five-Cycle in a Specified Order
Let \(G=(V,E)\) have \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,45,51\}\). Use the order \(1,3,5,2,4\). In the table, the previously colored neighbors are determined from the edge list, not from which vertices happen to have appeared consecutively in the order.
| Vertex | Previously colored neighbors and colors | Forbidden colors | Available colors and choice |
|---|---|---|---|
| \(1\) | None | \(\varnothing\) | \(1,2,\dots\); choose \(1\) |
| \(3\) | None; its neighbors are \(2,4\) | \(\varnothing\) | \(1,2,\dots\); choose \(1\) |
| \(5\) | \(1:1\) | \(\{1\}\) | \(2,3,\dots\); choose \(2\) |
| \(2\) | \(1:1,\ 3:1\) | \(\{1\}\) | \(2,3,\dots\); choose \(2\) |
| \(4\) | \(3:1,\ 5:2\) | \(\{1,2\}\) | \(3,4,\dots\); choose \(3\) |
The final classes are \(\{1,3\}\), \(\{5,2\}\), and \(\{4\}\), so the greedy color count is three. Check all five edges: \(12\) has colors \(1,2\); \(23\) has \(2,1\); \(34\) has \(1,3\); \(45\) has \(3,2\); and \(51\) has \(2,1\). Thus the result is proper. The output count is three because the labels used are \(1,2,3\). This calculation reports the count produced by this run; the definition of greedy coloring does not turn that count, by itself, into a proof of optimality.
Worked Example: A Four-Cycle, a Pendant Vertex, and an Isolated Vertex
Let \(G=(V,E)\) have \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,13,24,34,45\}\). Vertices \(1,2,4,3\) make a four-cycle, \(5\) is attached to \(4\), and \(6\) is isolated. Use the order \(1,2,3,4,5,6\).
| Vertex | Previously colored neighbors and colors | Forbidden colors | Available colors and choice |
|---|---|---|---|
| \(1\) | None | \(\varnothing\) | \(1,2,\dots\); choose \(1\) |
| \(2\) | \(1:1\) | \(\{1\}\) | \(2,3,\dots\); choose \(2\) |
| \(3\) | \(1:1\) | \(\{1\}\) | \(2,3,\dots\); choose \(2\) |
| \(4\) | \(2:2,\ 3:2\) | \(\{2\}\) | \(1,3,4,\dots\); choose \(1\) |
| \(5\) | \(4:1\) | \(\{1\}\) | \(2,3,\dots\); choose \(2\) |
| \(6\) | None; it is isolated | \(\varnothing\) | \(1,2,\dots\); choose \(1\) |
The color classes are \(\{1,4,6\}\) and \(\{2,3,5\}\). Check the edge list: \(12\) and \(13\) join colors \(1\) and \(2\); \(24\) and \(34\) join \(2\) and \(1\); and \(45\) joins \(1\) and \(2\). Hence the coloring is proper and uses two colors. Since the graph has at least one edge, a proper coloring cannot give every vertex the same color, so at least two colors are necessary. This example therefore also has \(\chi(G)=2\). The isolated vertex creates no forbidden color and can reuse color \(1\).
Reading and Checking a Trace
A reliable hand calculation follows the same checklist at every step:
- Identify the current vertex’s neighbors from the edge list.
- Keep only those neighbors that occur earlier in the specified order.
- Record their assigned colors and collect the distinct colors in the forbidden set.
- Choose the least positive integer outside that set.
- After the last step, check every edge and count the labels used.
Repeated neighbor colors are listed only once in the forbidden set. In the third example, vertex \(4\) has two previously colored neighbors, \(2\) and \(3\), but both have color \(2\). Its forbidden set is therefore \(\{2\}\), not a set containing two copies of \(2\). Color \(1\) is available and is the greedy choice.
Common Mistake: Looking at Only the Last Neighbor
In the first example, when coloring \(c\), the previously colored neighbors are both \(a\) and \(b\), with colors \(1\) and \(2\). A mistaken trace might inspect only the immediately preceding vertex \(b\), conclude that color \(1\) is available, and assign \(c\) color \(1\). That calculation misses the edge \(ac\): \(a\) already has color \(1\), so the proposed assignment makes the endpoints of \(ac\) equal in color. The correction is to use the full edge list, identify both colored neighbors, form the forbidden set \(\{1,2\}\), and assign \(c\) color \(3\).
A second useful distinction is between the greedy color count and the chromatic number. The trace always gives a proper coloring, so it supplies an upper bound on \(\chi(G)\); it does not automatically supply a matching lower bound. A lower bound must be justified separately, for example by identifying a clique. In the first example, the triangle provides that lower bound. In the third, the existence of an edge gives a lower bound of two, matching the displayed coloring.
Check Your Understanding
For each question, show the relevant neighbor-color calculation rather than giving only the final color count.
- For \(V=\{p,q,r\}\), \(E=\{pq,qr\}\), and order \(q,p,r\), record each greedy color and the final color count.
- For \(V=\{1,2,3,4\}\), \(E=\{12,13,14,23\}\), and order \(1,2,3,4\), list the forbidden set at each step and check the final coloring against every edge.
- Explain why an isolated vertex receives color \(1\) if it is the first vertex, and why it can receive color \(1\) later if no previously colored neighbor forbids that color.
- Give the two reasons that the coloring in the first worked example proves \(\chi(G)=3\), rather than merely showing that greedy used three colors.
- In a greedy trace, a vertex receives color \(4\). What must be true about colors \(1,2,3\) on its previously colored neighbors? Justify your answer from the least-available-color rule.