# Chapter 70. Greedy Coloring

# Chapter 70. Greedy Coloring

Greedy coloring is the simplest general method for producing a proper vertex coloring of a graph. It colors the vertices one at a time. At each step, it chooses a color that does not conflict with the colors already assigned to neighboring vertices.

The method is local. It does not solve the whole coloring problem at once. It makes a sequence of immediate choices. This makes the algorithm fast and useful, but it also makes the result depend strongly on the order in which the vertices are processed. Greedy coloring can be computed in linear time for a fixed vertex order, but it does not generally produce a minimum coloring.

## 70.1 The Basic Algorithm

Let

$$
G=(V,E)
$$

be a graph, and let the vertices be ordered as

$$
v_1,v_2,\ldots,v_n.
$$

The greedy coloring algorithm processes the vertices in this order.

When the algorithm reaches \(v_i\), some of its earlier neighbors may already have colors. The algorithm assigns to \(v_i\) the smallest positive integer that has not been used on those earlier neighbors.

Thus, if the available colors are

$$
1,2,3,\ldots,
$$

then \(v_i\) receives the least color not appearing among the colored vertices adjacent to \(v_i\).

The result is always a proper coloring. Indeed, when an edge \(v_iv_j\) is considered, suppose \(i<j\). When \(v_j\) is colored, the vertex \(v_i\) has already been colored, so \(v_j\) is forbidden from receiving the color of \(v_i\).

## 70.2 Pseudocode

The algorithm can be written as follows.

```text
Greedy-Color(G, order)
    for each vertex v in order:
        used := colors assigned to already-colored neighbors of v
        assign v the smallest color not in used
    return the coloring
```

This version uses an infinite conceptual list of colors. In implementation, only finitely many colors are ever needed.

For a graph with maximum degree \(\Delta(G)\), the algorithm never needs more than

$$
\Delta(G)+1
$$

colors. At a vertex \(v\), at most \(d(v)\le \Delta(G)\) colors can be forbidden by its neighbors. Hence at least one of the first \(\Delta(G)+1\) colors is available.

## 70.3 Example: A Path

Consider the path

$$
v_1-v_2-v_3-v_4.
$$

Use the natural order

$$
v_1,v_2,v_3,v_4.
$$

The greedy algorithm gives:

| Step | Vertex | Forbidden colors | Assigned color |
|---:|---|---|---:|
| 1 | \(v_1\) | none | 1 |
| 2 | \(v_2\) | 1 | 2 |
| 3 | \(v_3\) | 2 | 1 |
| 4 | \(v_4\) | 1 | 2 |

The resulting coloring uses two colors. This is optimal, since the path has at least one edge and is bipartite.

## 70.4 Example: A Cycle

For the even cycle \(C_6\), order the vertices cyclically:

$$
v_1,v_2,v_3,v_4,v_5,v_6.
$$

Greedy coloring assigns colors

$$
1,2,1,2,1,2.
$$

The coloring is proper and uses two colors.

For the odd cycle \(C_5\), the same ordering gives

$$
1,2,1,2,3.
$$

The final vertex is adjacent to both \(v_1\) and \(v_4\). These already have colors 1 and 2, so the final vertex requires color 3.

This agrees with the fact that odd cycles have chromatic number 3.

## 70.5 Dependence on Ordering

The same graph can receive different greedy colorings under different vertex orders. This is the main weakness of the method.

A good order may produce an optimal coloring. A poor order may use more colors than necessary. The study of greedy coloring therefore includes the study of vertex ordering strategies. Common strategies include ordering high-degree vertices early, using smallest-last orderings, and using adaptive rules based on current constraints.

The algorithm itself is deterministic once the order is fixed. The uncertainty lies in the choice of order.

## 70.6 A Poor Ordering Example

Consider the bipartite graph with vertices

$$
a_1,a_2,b_1,b_2
$$

and edges

$$
a_1b_2,\quad a_2b_1,\quad a_2b_2.
$$

This graph is bipartite with parts

$$
A=\{a_1,a_2\},\qquad B=\{b_1,b_2\}.
$$

Therefore it is 2-colorable.

Now use the order

$$
a_1,b_1,a_2,b_2.
$$

Greedy coloring proceeds as follows:

| Step | Vertex | Colored neighbors | Assigned color |
|---:|---|---|---:|
| 1 | \(a_1\) | none | 1 |
| 2 | \(b_1\) | none | 1 |
| 3 | \(a_2\) | \(b_1\) has color 1 | 2 |
| 4 | \(b_2\) | \(a_1\) has color 1, \(a_2\) has color 2 | 3 |

The algorithm uses three colors, even though the graph is 2-colorable.

This example shows that greedy coloring can fail to find the chromatic number.

## 70.7 Correctness

Greedy coloring always produces a proper coloring.

To prove this, let \(uv\in E\). Suppose \(u\) appears before \(v\) in the chosen order. When \(v\) is colored, \(u\) is already colored and is one of the colored neighbors of \(v\). Therefore the color of \(u\) is forbidden for \(v\).

Hence

$$
c(u)\ne c(v).
$$

Since this holds for every edge, the coloring is proper.

This proof does not depend on the ordering. Every ordering produces a proper coloring.

## 70.8 The Maximum Degree Bound

Let \(\Delta(G)\) be the maximum degree of \(G\). Greedy coloring proves the standard bound

$$
\chi(G)\le \Delta(G)+1.
$$

Indeed, fix any ordering of the vertices and run greedy coloring using colors

$$
1,2,\ldots,\Delta(G)+1.
$$

When a vertex \(v\) is colored, at most \(d(v)\) neighboring vertices have already been colored. Since

$$
d(v)\le \Delta(G),
$$

at most \(\Delta(G)\) colors are forbidden. Therefore one of the \(\Delta(G)+1\) colors remains available.

This proves that the graph can be colored with at most \(\Delta(G)+1\) colors. The argument is constructive: it gives an algorithm as well as a proof.

## 70.9 Sharpness of the Bound

The bound

$$
\chi(G)\le \Delta(G)+1
$$

cannot be improved for all graphs.

For the complete graph \(K_n\),

$$
\Delta(K_n)=n-1
$$

and

$$
\chi(K_n)=n=\Delta(K_n)+1.
$$

For an odd cycle \(C_{2m+1}\),

$$
\Delta(C_{2m+1})=2
$$

and

$$
\chi(C_{2m+1})=3=\Delta(C_{2m+1})+1.
$$

Thus complete graphs and odd cycles attain the bound.

Brooks' Theorem later refines this result: except for complete graphs and odd cycles, every connected graph satisfies

$$
\chi(G)\le \Delta(G).
$$

## 70.10 Largest-First Ordering

A common heuristic is to color high-degree vertices before low-degree vertices.

The reason is simple. High-degree vertices impose many constraints. If they are colored early, later vertices can adapt to them. If they are colored late, they may face many already-used colors and require a new color.

The largest-first strategy orders vertices by nonincreasing degree:

$$
d(v_1)\ge d(v_2)\ge \cdots \ge d(v_n).
$$

This method is easy to implement. It often improves over an arbitrary order. However, it does not guarantee an optimal coloring.

Largest-first ordering is a heuristic, not a theorem of optimality.

## 70.11 Smallest-Last Ordering

Another important ordering is the smallest-last ordering.

It is constructed backward:

1. Choose a vertex of minimum degree.
2. Remove it from the graph.
3. Repeat on the remaining graph.
4. Place removed vertices in reverse order.

The largest minimum degree encountered during this removal process is called the degeneracy of the graph.

If \(G\) has degeneracy \(d\), then greedy coloring with a smallest-last order uses at most

$$
d+1
$$

colors. This can improve substantially on the bound \(\Delta(G)+1\), especially for sparse graphs. Degeneracy orderings can be computed in linear time and give a standard practical improvement over arbitrary greedy coloring.

## 70.12 DSatur

DSatur is an adaptive greedy coloring method. Instead of fixing the whole vertex order in advance, it chooses the next vertex during the coloring process.

At each step, DSatur chooses an uncolored vertex with the largest number of distinct colors already present among its colored neighbors. This number is called the saturation degree.

If there is a tie, one common rule chooses a vertex of largest ordinary degree.

The intuition is that vertices with many forbidden colors are more constrained and should be handled first.

DSatur often performs well in practice and can be optimal on several special graph classes, but it remains a heuristic for general graphs.

## 70.13 Greedy Coloring and Independent Sets

Every color class produced by greedy coloring is an independent set.

For each color \(i\), define

$$
V_i=\{v\in V:c(v)=i\}.
$$

If two adjacent vertices both belonged to \(V_i\), the coloring would not be proper. Therefore \(V_i\) is independent.

Greedy coloring may also be viewed as building independent sets in sequence. Color 1 is assigned to as many vertices as possible in the chosen order. Color 2 is then assigned to vertices that could not receive color 1 but can avoid conflicts with earlier color-2 vertices, and so on.

This connects greedy coloring with the partition view of graph coloring.

## 70.14 Time Complexity

For a fixed vertex ordering, greedy coloring is efficient.

Using adjacency lists, the algorithm examines the already-colored neighbors of each vertex. Across the whole run, this accounts for work proportional to the number of edges, plus work for initializing vertices and colors.

With appropriate data structures, the running time is

$$
O(|V|+|E|).
$$

This is one of the reasons greedy coloring is widely used. Exact graph coloring can be computationally hard, but greedy coloring gives a feasible coloring quickly.

## 70.15 Applications

Greedy coloring is useful when a valid coloring is needed quickly and optimality is less important.

Typical applications include:

| Application | Vertex meaning | Edge meaning | Color meaning |
|---|---|---|---|
| Exam scheduling | Exam | Shared student | Time slot |
| Register allocation | Variable | Simultaneous live range | Register |
| Frequency assignment | Transmitter | Interference | Frequency |
| Task scheduling | Task | Conflict | Time block |
| Resource allocation | Job | Shared resource conflict | Resource group |

In compiler register allocation, greedy coloring can be used on interference graphs, where adjacent vertices represent values that cannot occupy the same register. Greedy coloring has also been applied to scheduling and register allocation problems.

## 70.16 Limitations

Greedy coloring has three main limitations.

First, it may use more colors than necessary.

Second, its performance depends on vertex ordering.

Third, finding an order that guarantees an optimal greedy coloring is generally as hard as solving the coloring problem itself. Although there always exists an order that makes greedy coloring optimal, finding such an order is difficult in general.

For this reason, greedy coloring is best understood as a fast constructive method and as a proof tool, rather than as a complete solution to graph coloring.

## 70.17 Summary

Greedy coloring is a sequential algorithm for proper vertex coloring.

Its main features are:

| Feature | Description |
|---|---|
| Input | Graph and vertex order |
| Rule | Use the smallest color not used by colored neighbors |
| Output | Proper vertex coloring |
| Strength | Fast and simple |
| Weakness | Order-dependent |
| General bound | At most \(\Delta(G)+1\) colors |
| Sparse graph bound | At most degeneracy \(+1\) colors with smallest-last ordering |

Greedy coloring is one of the first examples of an algorithmic proof in graph theory. It proves the maximum-degree coloring bound, gives practical colorings, and motivates deeper questions about ordering, structure, and optimality.

## 70.18 Exercises

1. Apply greedy coloring to \(P_5\) using the natural path order.

2. Apply greedy coloring to \(C_5\) using the cyclic order.

3. Find an ordering of \(C_6\) for which greedy coloring uses two colors.

4. Prove that greedy coloring always produces a proper coloring.

5. Prove that greedy coloring uses at most \(\Delta(G)+1\) colors.

6. Give a bipartite graph and a vertex order for which greedy coloring uses three colors.

7. Apply largest-first greedy coloring to the star \(K_{1,n}\).

8. Construct a graph where largest-first ordering is not optimal.

9. Compute a smallest-last ordering for a tree.

10. Prove that every tree has a greedy coloring using at most two colors under a suitable ordering.

11. Explain why a poor vertex ordering can force unnecessary colors.

12. Compare greedy coloring with optimal coloring for \(K_n\).

13. Describe the DSatur rule in your own words.

14. Show that every color class in a greedy coloring is an independent set.

15. Give an application where a fast non-optimal coloring is useful.