Skip to content
Tutorials Center
My learning

Topics

Lesson 20 of 36 ยท Coloring and Matching

Greedy Coloring and Brooks' Theorem

Color graphs fast with the greedy algorithm, compare vertex orderings (Welsh-Powell, smallest-last, DSATUR) and learn the degree bounds that Brooks' theorem gives.

Exact coloring is NP-hard, so in practice we use fast heuristics that give a good, though not always optimal, answer. The simplest is the greedy algorithm: visit the vertices in some order and give each one the smallest color not already used by a colored neighbor. It runs in time proportional to the number of edges, and its quality depends entirely on the order you choose.

In this lesson you will implement greedy coloring, see how a bad order can waste colors, compare three well-known orderings, and learn the theorem that says how many colors greedy needs at most.

The greedy algorithm

For each vertex v in the chosen order, look at the colors of its already-colored neighbors and pick the smallest non-negative integer not among them. A vertex with d neighbors can never be blocked by more than d colors, so greedy never needs a color number above d.

This gives the first general upper bound: ฯ‡(G) โ‰ค ฮ”(G) + 1, where ฮ” is the maximum degree. Complete graphs and odd cycles need exactly that many colors.

Python Greedy coloring: the order matters

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The crown graph is bipartite, yet an unlucky order uses n colors. The interleaved order colors a0 and b0 (not adjacent) the same, then a1 has to avoid b0's color... and the damage accumulates. An order that handles one whole side first gives the optimal 2 colors. The lesson is that greedy is optimal for some order, but finding that order is as hard as the original problem.

Welsh-Powell sorts vertices by decreasing degree. High-degree vertices have the most conflicts, so they pick first while many colors are free.

Smallest-last (degeneracy order) repeatedly removes a vertex of minimum degree from the remaining graph and records the removal order; coloring then happens in reverse removal order. Each vertex, when colored, has at most d earlier neighbors, where d is the graph's degeneracy, so greedy uses at most d + 1 colors. Planar graphs have degeneracy at most 5, giving a quick proof that planar graphs are 6-colorable (see planar graphs).

DSATUR (degree of saturation) is dynamic: always color next the vertex whose neighbors already show the most distinct colors, breaking ties by degree. It is optimal on bipartite graphs, cycles and wheels, and is the standard fast heuristic.

flowchart TD
    A["Pick next vertex"] --> B{"Static or dynamic?"}
    B -->|"static"| C["Welsh-Powell: sort by degree once"]
    B -->|"static"| D["Smallest-last: peel low-degree vertices"]
    B -->|"dynamic"| E["DSATUR: most distinct neighbor colors"]
    C --> F["Assign smallest free color"]
    D --> F
    E --> F

All three orderings feed the same greedy assignment step.

Python Compare Welsh-Powell, smallest-last and DSATUR

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All three outputs are proper colorings, and all respect the ฮ” + 1 bound, usually using far fewer colors than that bound. On these random graphs DSATUR matches or beats the other two.

Brooks' theorem

The bound ฮ” + 1 is tight for complete graphs and odd cycles. Brooks' theorem says those are the only exceptions:

If G is connected and is neither a complete graph nor an odd cycle, then ฯ‡(G) โ‰ค ฮ”(G).

So for almost every connected graph, ฮ” colors suffice. The proof is constructive: order vertices so that every vertex except the last has a neighbor that comes later, and make the last vertex see two neighbors with the same color. A degree-3 graph that is not K4, for example, is always 3-colorable.

Python Check Brooks' bound on small graphs by brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

K4 has ฮ” = 3 but ฯ‡ = 4, and C7 has ฮ” = 2 but ฯ‡ = 3: the two exceptions. The Petersen graph has ฮ” = 3 and ฯ‡ = 3, exactly as the theorem allows.

When to stop using heuristics

Real systems often run greedy or DSATUR first, then improve with local search (recoloring a vertex, swapping two color classes called a Kempe chain) or hand the instance to a SAT or integer-programming solver for an exact answer. For graphs with a few hundred vertices an exact solver is usually still feasible.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Greedy coloring never needs a color number larger than which value?

    A vertex has at most ฮ” neighbors, so at most ฮ” colors are blocked and one of the colors 0..ฮ” is free. That gives at most ฮ” + 1 colors in total.
  2. 2. Which graphs need all ฮ” + 1 colors according to Brooks' theorem (connected case)?

    Brooks' theorem lists exactly two exceptions to ฯ‡ โ‰ค ฮ”, namely complete graphs and odd cycles.
  3. 3. What does the smallest-last ordering guarantee?

    Each vertex has at most d earlier neighbors in the coloring order, where d is the degeneracy, so greedy needs at most d + 1 colors. It is not always optimal.
  4. 4. How does DSATUR choose the next vertex?

    DSATUR picks the vertex with the highest saturation degree, breaking ties by ordinary degree, because that vertex has the fewest remaining choices.

Summary

  • Greedy coloring assigns each vertex the smallest free color and runs in linear time, but the vertex order decides quality.
  • Every graph satisfies ฯ‡ โ‰ค ฮ” + 1; smallest-last gives ฯ‡ โ‰ค degeneracy + 1.
  • Welsh-Powell, smallest-last and DSATUR are the standard orderings; DSATUR is optimal on bipartite graphs.
  • Brooks' theorem: a connected graph that is neither complete nor an odd cycle has ฯ‡ โ‰ค ฮ”.

Next: Edge Coloring and the Chromatic Polynomial