Graph Coloring (Greedy)

Graph Coloring asks you to paint every vertex of a graph so that no edge connects two vertices of the same color, using as few colors as possible. Finding the true minimum is NP-hard, but a simple greedy pass gives a fast, reasonable coloring — and it is a clean interview exercise in processing things in order and picking the smallest available option.

The slow way first

You could try every possible assignment of colors to vertices and keep the one that uses the fewest while staying valid. With k colors and n vertices that is k^n combinations — exponential, and hopeless for anything but tiny graphs. The exact chromatic number really is NP-hard, so brute force is the honest baseline, not a practical method.

The question to ask: can I make one decision per vertex and never look back? For a quick, good-enough answer, yes — and that is exactly what greedy does.

The idea: smallest unused color

Walk the vertices in the given order. For the current vertex v, look at the vertices it connects to that are already colored, and collect the set of colors they use. Then pick the smallest non-negative integer that is not in that set and give it to v. Move on. Because we only ever avoid colors that conflict, the result is always valid.

The greedy choice is local: it never reconsiders an earlier vertex. That makes it fast, but the color count depends on the ordering — a different order can use fewer (or more) colors.

Walk through it

Step through the animation. The current vertex glows, its already-colored neighbors are marked, and we read off the smallest color they leave free. A has no colored neighbors, so it takes 0. B touches A=0, so it takes 1. C touches A=0, so it takes 1. D touches B=1 and C=1, so 0 is free. E touches B=1 and D=0, so the smallest free color is 2. The running colors used counter ends at three.

Pseudocode

color = empty map
for v in order:
    used = empty set
    for nb in neighbors(v):
        if nb already has a color:
            add color[nb] to used
    c = 0
    while c is in used:
        c = c + 1
    color[v] = c            # smallest color no neighbor uses
return color

The Python solution

def greedy_coloring(graph, order):
    color = {}
    for v in order:
        used = set()
        for nb in graph[v]:
            if nb in color:
                used.add(color[nb])
        c = 0
        while c in used:
            c += 1
        color[v] = c
    return color

• graph is an adjacency map (vertex → list of neighbors); order is the sequence we process vertices in.
• For each v we build used, the set of colors taken by its already-colored neighbors (if nb in color).
• The while c in used loop walks 0, 1, 2, ... and stops at the first color not in used — the smallest available.
• We assign color[v] = c and never revisit it. One decision per vertex.

Complexity

Greedy touches each vertex once and each edge a constant number of times, so it runs in O(V + E). It does not guarantee the fewest possible colors, but it never uses more than maxDegree + 1.

When this pattern shows up

Practice