Graph Coloring

What is this?

Think of seating guests at a dinner where some pairs simply cannot sit at the same table. Graph coloring is the art of assigning each guest a "color" (a table) so that no two guests who clash get the same one. The most common interview flavor asks the simplest version: can everyone be split into just two groups so that every clashing pair lands on opposite sides? You answer it by walking the graph and painting neighbors the opposite color, watching for a contradiction.

💡 Fun fact: the famous Four Color Theorem — that any map can be colored with just four colors so no neighboring regions match — was the first major mathematical proof to rely on a computer, in 1976. It checked nearly 2000 special cases by hand-built program, sparking a long debate over whether a proof a human cannot fully verify really counts.

🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: color the nodes so no edge joins two same-colored nodes. Asking "can I do it with k colors?" is generally NP-hard — but the one case interviewers love, k = 2, is easy and equivalent to a famous property: a graph is 2-colorable if and only if it's bipartite, if and only if it has no odd-length cycle. That check is a single BFS/DFS that paints nodes alternating colors and watches for a clash.

1. What "graph coloring" really means

A proper coloring assigns each vertex a color such that adjacent vertices differ. The minimum number of colors a graph needs is its chromatic number χ. Coloring formalizes "things that conflict must be kept apart":

The 2-color case has a clean characterization. Walk the graph painting each node the opposite color of the node you came from. If you ever reach an already-painted node and it has the same color as the current node, you've closed an odd cycle — and the graph is not bipartite (not 2-colorable). No clash anywhere ⇒ it is.

⚠️ The general problem is brutal: deciding 3-colorability is NP-complete, and computing χ exactly is intractable for large graphs. Don't reach for an exact general solver in an interview unless the graph is tiny — recognize when you're really being asked the bipartite (2-color) question.

2. Where you'll actually meet this

Coloring is the math behind "allocate scarce resources so conflicting users don't collide":

• Compiler register allocation. Variables live at the same time interfere; an edge joins them, and colors are CPU registers. A valid coloring fits the variables into registers without two live values sharing one — the textbook application (often via Chaitin's graph-coloring allocator).
• Scheduling & timetabling. Exams/meetings that share a student or room conflict (edge); colors are time slots. χ = minimum number of slots with no clash. Bipartite checks confirm "can this all fit in two rounds?"
• Frequency / channel assignment. Cell towers or Wi-Fi access points that overlap interfere; colors are frequencies/channels, kept different for neighbours.
• Map coloring. Adjacent regions get different colors — the Four Color Theorem guarantees any planar map needs at most 4.
• Distributed systems & bipartite matching. Bipartite detection underpins matching (jobs↔workers, ads↔slots), two-phase conflict graphs, and detecting "two-sided" structure in networks.

If a problem says two groups / no two adjacent the same / can this be split in two / assign without conflicts — coloring (usually bipartite) is the lens.

3. The coloring toolkit

1. Recognize 2-color = bipartite = no odd cycle. The moment "k colors" is "k = 2" (or "split into two teams"), drop coloring machinery and run a bipartite check.
2. BFS/DFS with alternating colors. Paint a start node 0, paint each neighbour 1 - color. A neighbour already painted the same color ⇒ not bipartite.
3. Cover every component. Disconnected graphs need a fresh start (and a fresh color seed) per uncolored component — loop over all nodes.
4. Greedy coloring for the general case. Order the vertices and give each the smallest color not used by its neighbours. Fast and simple, but not optimal — it can use more colors than χ. Good for a quick feasible answer, not a minimum.
5. DSATUR / backtracking for exactness on small graphs. When you truly need χ and the graph is small, saturation-degree ordering or backtracking finds it — but accept the exponential worst case.

The interview workhorse — bipartite detection (BFS):

from collections import deque

def is_bipartite(graph):
    color = {}                          # node -> 0 or 1
    for start in graph:
        if start in color:
            continue                    # already handled in an earlier component
        color[start] = 0
        q = deque([start])
        while q:
            u = q.popleft()
            for v in graph[u]:
                if v not in color:
                    color[v] = 1 - color[u]   # opposite color
                    q.append(v)
                elif color[v] == color[u]:    # adjacent + same color
                    return False              # odd cycle -> not 2-colorable
    return True

4. A 30-second worked example

Is this graph bipartite? Edges: 0-1, 1-2, 2-3, 3-0 (a 4-cycle) plus 0-2:

Remove edge 0-2 and it's a clean 4-cycle: colors 0,1,0,1 around the ring, no clash ⇒ bipartite. One BFS, one extra bit per node — that's the entire test.

5. Problems / when to reach for it

• Is Graph Bipartite? — the direct 2-coloring check above. O(V + E).
• Possible Bipartition — "split people into two groups so disliked pairs are separated": build the dislike graph, test bipartite. Same algorithm.
• Flower Planting With No Adjacent / scheduling-style problems — small fixed palette + adjacency constraints → greedy coloring.
• Reach for it whenever conflicts form a graph and you must partition into non-conflicting classes. Bipartite check: O(V + E) time, O(V) space. General optimal coloring: NP-hard — don't promise a minimum-color solution fast.

6. Common pitfalls 🚫

• Skipping disconnected components. A bipartite check that starts from one node misses other components — loop over every vertex.
• Confusing "2 colors" with "any k colors." The easy O(V+E) result is only the bipartite case; general k-coloring is NP-hard. Know which you're being asked.
• Forgetting the same-color edge check. Painting opposite colors isn't enough — you must detect when an already-colored neighbour clashes. That clash is the whole point.
• Directed-edge confusion. Standard coloring/bipartite reasoning is for undirected adjacency; if edges are directed, ignore direction for the conflict graph.
• Self-loops. A node adjacent to itself can never be properly colored — handle or reject it.

7. Key takeaways

1. Coloring = keep conflicting things apart. Edges mean "must differ"; colors are the resource (register, time slot, frequency).
2. 2-color ⟺ bipartite ⟺ no odd cycle — and it's a single O(V + E) BFS/DFS that paints alternating colors and catches clashes.
3. Cover all components, seed a fresh color each time, and check that already-colored neighbours don't match.
4. General coloring is NP-hard. Greedy gives a quick feasible coloring (not minimal); exact χ needs backtracking/DSATUR and only on small graphs.
5. The pattern powers register allocation, scheduling, and frequency assignment — which is why the bipartite check is a staple interview question dressed up as "split into two groups."