Assigning colors so adjacent vertices differ. Chromatic number.
Quick unlock - significant prerequisite investment but simple final step. Verify prerequisites first.
Graph coloring looks like a simple puzzle—paint vertices so neighbors clash—but it quietly connects scheduling, register allocation, planar maps, and the boundary between what we can solve efficiently and what’s NP-complete.
A proper vertex coloring assigns colors to vertices so adjacent vertices differ. The chromatic number χ(G) is the minimum number of colors needed. A coloring is equivalently a partition of V into independent sets. Finding χ(G) is NP-hard in general, but there are strong bounds, special graph classes with efficient algorithms, and practical heuristics that often work well.
Many real problems have the same underlying constraint: some pairs of items cannot share the same resource.
Graph coloring turns “cannot share” constraints into edges, and “resources” into colors.
Let G = (V, E) be an undirected graph.
A proper vertex coloring is a function
c : V → {1, 2, …, k}
such that for every edge (u, v) ∈ E,
c(u) ≠ c(v).
If such a c exists, we say G is k-colorable.
The chromatic number χ(G) is the smallest k for which G is k-colorable:
χ(G) = min { k : G is k-colorable }.
This is an optimization version of a decision problem:
You already know NP-completeness; graph coloring is a classic member of that family.
Thinking of color i as “time slot i,” the constraint c(u) ≠ c(v) says: if two vertices conflict (edge), they can’t occupy the same slot.
This viewpoint will matter later when we talk about reductions and why coloring is hard.
1) Edgeless graph (E = ∅): no constraints. Every vertex can share the same color.
χ(G) = 1 (unless V is empty; conventions vary, but typically χ(∅) = 0).
2) Complete graph Kₙ: every pair conflicts.
χ(Kₙ) = n.
Those are extremes: from “everything compatible” to “nothing compatible.” Most graphs live in between.
Given a coloring c with k colors, define the set of vertices with each color:
Cᵢ = { v ∈ V : c(v) = i }.
Each Cᵢ is called a color class.
We’ll soon see that each color class must be an independent set (no edges inside it), which gives a powerful alternate lens.
The function definition c : V → {1..k} is clean, but it hides structure.
A k-coloring doesn’t just label vertices—it groups them into k buckets. The key is that each bucket must be internally conflict-free.
This turns coloring into a partition problem:
Coloring = partition V into independent sets.
This perspective is often the quickest route to:
A set S ⊂ V is an independent set if ∀u, v ∈ S, (u, v) ∉ E.
Now connect that to coloring.
Claim: In any proper coloring, each color class Cᵢ is an independent set.
Reason: Suppose there is an edge (u, v) with u, v ∈ Cᵢ. Then c(u) = c(v) = i, violating properness.
So properness ⇔ “no edges inside any color class.”
We can make the equivalence explicit.
Proposition: G is k-colorable iff V can be partitioned into k independent sets.
(⇒) Given a k-coloring, sets C₁, …, C_k partition V, and each Cᵢ is independent (as shown).
(⇐) Given a partition V = I₁ ⊔ I₂ ⊔ … ⊔ I_k into independent sets, define c(v) = i for v ∈ Iᵢ. Any edge (u, v) cannot lie within the same Iᵢ (independence), so c(u) ≠ c(v). Proper coloring.
This equivalence is simple, but it unlocks many bounds.
A clique is a set of vertices all mutually adjacent.
If a graph contains a clique of size ω(G), then all those vertices must receive different colors.
So:
χ(G) ≥ ω(G).
This is often the first lower bound you try.
Let α(G) be the size of a maximum independent set.
If each color class is an independent set of size at most α(G), then k color classes cover at most k·α(G) vertices.
To cover all |V| vertices, we need:
k·α(G) ≥ |V| ⇒ k ≥ |V| / α(G).
Thus:
χ(G) ≥ ⌈ |V| / α(G) ⌉.
This bound is sometimes stronger than the clique bound (especially in sparse graphs).
A simple way to build a coloring is to order vertices and assign each vertex the smallest available color not used by its colored neighbors. This is greedy coloring.
Greedy always succeeds with at most Δ(G) + 1 colors, where Δ(G) is maximum degree.
Reason (local constraint): when coloring a vertex v, at most Δ(G) neighbors are already colored, so at most Δ(G) colors are “blocked.” With Δ(G) + 1 colors, some color is free.
So:
χ(G) ≤ Δ(G) + 1.
This bound is not always tight, but it’s universal and constructive.
Brooks’ theorem (informal): For a connected graph that is neither a complete graph nor an odd cycle,
χ(G) ≤ Δ(G).
This is a deep strengthening of the greedy Δ + 1 bound.
You don’t need the proof yet, but you should remember the shape: only two families (cliques, odd cycles) force Δ + 1 colors.
Let Ḡ be the complement graph: same vertices, edges are exactly the non-edges of G.
In Ḡ, a clique corresponds to an independent set in G, and vice versa.
That means:
This is part of why coloring is entangled with other NP-hard problems: clique and independent set are also NP-hard.
The partition view helps you reason about coloring without “colors” at all:
In practice, you’ll often want:
That is exactly χ(G). Unfortunately, computing χ(G) is NP-hard. So the learning goal is twofold:
1) know what can be solved efficiently (special cases, approximations, bounds)
2) know how to reason about hardness and reductions
Given (G, k), ask whether χ(G) ≤ k.
The shift from 2 to 3 is one of the most important “phase transitions” in graph algorithms.
A graph is 2-colorable iff it is bipartite iff it has no odd cycle.
BFS-based 2-coloring algorithm:
This is polynomial-time and illustrates a theme: adding just one more color destroys tractability.
You already know reductions from SAT / 3-SAT. The typical plan for showing 3-COLORING NP-complete is:
We won’t re-derive the full gadget construction in detail here, but you should internalize the shape:
This “encoding constraints as edges” idea mirrors real applications.
If you can compute χ(G), you can answer k-COLORING by checking whether χ(G) ≤ k.
So CHROMATIC NUMBER is NP-hard.
Also, k-COLORING is NP-complete for k ≥ 3, so unless P = NP, we should not expect a general efficient algorithm.
Even approximating χ(G) is difficult.
Some key facts (stated informally):
So in practice you combine:
Even though finding χ(G) is hard, verifying a given coloring uses O(|E|) checks:
For each edge (u, v) ∈ E, confirm c(u) ≠ c(v).
So “G is k-colorable” is in NP: the certificate is the coloring itself.
This is the usual NP pattern: hard to find, easy to check.
You can also treat k as a parameter.
Even without full parameterized theory, the intuition is useful:
Graph coloring is a “complexity landmark.”
In applications you rarely see “color this graph.” You see:
The reduction recipe:
1) Make a vertex for each item to be assigned a resource.
2) Add an edge between items that cannot share a resource.
3) A color is a resource bucket.
Then χ(G) is the minimum number of resource buckets.
Vertices = exams.
Edge between exams that share at least one student.
Color = time slot.
Proper coloring ensures no student has two exams at the same time.
Vertices = program variables.
Edge if two variables are simultaneously live.
Color = CPU register.
If χ(G) exceeds available registers, compilers may “spill” variables to memory.
Vertices = transmitters.
Edge if too close in space/spectrum to share frequency.
Color = frequency channel.
Because χ(G) is hard, real systems use heuristics.
Greedy depends heavily on vertex order.
Common orderings:
| Ordering | Idea | When it helps |
|---|---|---|
| Largest degree first | color high-degree constraints early | dense graphs |
| Smallest degree first | keep options open (sometimes) | sparse graphs |
| Degeneracy ordering | guarantees ≤ d + 1 colors where d is degeneracy | many real sparse graphs |
| DSATUR | choose vertex with highest “saturation” (distinct neighbor colors) | often near-optimal in practice |
A vertex with many differently colored neighbors has fewer remaining choices. Coloring it next reduces the chance of getting stuck and often reduces total colors.
DSATUR is also used in exact branch-and-bound solvers as a strong branching heuristic.
The general problem is hard, but structure can make it easy.
χ(G) is 1 or 2, found by BFS/DFS.
Graphs where vertices are intervals on a line, edges mean overlap.
χ(G) equals the size of the maximum clique ω(G), and optimal coloring can be found greedily by sorting intervals by start/end times.
Why: overlaps behave like “simultaneous resource usage,” and cliques capture peak overlap.
Graphs with no induced cycles of length ≥ 4.
They have a perfect elimination ordering. Using that ordering, greedy coloring is optimal, and again χ(G) = ω(G).
Planar graphs satisfy the Four Color Theorem:
χ(G) ≤ 4.
This matters when your conflict graph comes from geographic adjacency.
When you face a graph instance, useful quick diagnostics:
If lower and upper meet, you have χ(G) exactly.
Your BFS/DFS knowledge matters because:
Reductions are the language for explaining why k-coloring is hard:
This is one of the cleanest places to practice reduction thinking.
Let G be the cycle C₆ (6 vertices in a loop) and H be the cycle C₅ (5 vertices in a loop). Determine χ(C₆) and χ(C₅).
Step 1: Try 2-coloring C₆.
Label vertices v₁…v₆ in order around the cycle.
Assign c(v₁)=1.
Then to satisfy edges:
c(v₂)=2, c(v₃)=1, c(v₄)=2, c(v₅)=1, c(v₆)=2.
Now check the closing edge (v₆, v₁): c(v₆)=2 and c(v₁)=1, OK.
Step 2: Conclude χ(C₆)=2.
C₆ has edges, so χ(C₆) ≠ 1.
We exhibited a proper 2-coloring, so χ(C₆) ≤ 2.
Therefore χ(C₆)=2.
Step 3: Try the same on C₅.
Label v₁…v₅.
Set c(v₁)=1.
Then forced alternation gives:
c(v₂)=2, c(v₃)=1, c(v₄)=2, c(v₅)=1.
Now check the closing edge (v₅, v₁): c(v₅)=1 and c(v₁)=1, conflict.
Step 4: Conclude C₅ is not 2-colorable ⇒ χ(C₅) ≥ 3.
The conflict is unavoidable because the parity alternation around an odd cycle forces the last vertex to match the first.
Step 5: Show χ(C₅)=3 by constructing a 3-coloring.
For instance:
c(v₁)=1, c(v₂)=2, c(v₃)=1, c(v₄)=2, c(v₅)=3.
Now every edge has different colors, so χ(C₅) ≤ 3.
Thus χ(C₅)=3.
Insight: Cycles perfectly illustrate the jump from 2-colorable to needing 3: even cycles are bipartite (χ=2), odd cycles are not (χ=3). This is the simplest manifestation of “odd cycle obstruction.”
Consider a graph G with vertices {a,b,c,d,e} and edges forming a triangle on {a,b,c} plus edges (c,d), (d,e), (e,c). So {c,d,e} also forms a triangle except missing (c,e)? Actually edges include (c,d), (d,e), (e,c), so it is a triangle. The graph is two triangles sharing vertex c: triangle abc and triangle cde.
Step 1: Find a clique lower bound.
Vertices {a,b,c} form a clique of size 3.
Vertices {c,d,e} also form a clique of size 3.
So ω(G)=3 ⇒ χ(G) ≥ 3.
Step 2: Compute maximum degree Δ(G).
Deg(a)=2 (b,c)
Deg(b)=2 (a,c)
Deg(c)=4 (a,b,d,e)
Deg(d)=2 (c,e)
Deg(e)=2 (c,d)
So Δ(G)=4 ⇒ χ(G) ≤ Δ(G)+1=5 (universal bound).
Step 3: Try a greedy coloring to improve the upper bound.
Choose an order that starts with high degree: c, a, b, d, e.
Color c with 1.
Color a (adjacent to c) with 2.
Color b (adjacent to c and a): cannot use 1 (c), cannot use 2 (a) ⇒ use 3.
Color d (adjacent to c): cannot use 1 ⇒ can use 2.
Color e (adjacent to c and d): cannot use 1 (c), cannot use 2 (d) ⇒ can use 3.
Step 4: Conclude χ(G)=3.
We constructed a proper 3-coloring ⇒ χ(G) ≤ 3.
Combined with χ(G) ≥ 3 from the clique bound, we get χ(G)=3 exactly.
Insight: In many graphs, simple lower bounds (ω(G)) and a decent greedy upper bound meet quickly. When they do, you’ve solved an NP-hard problem instance without heavy machinery.
You have 6 exams: {M, P, C, H, B, E}. Conflicts (shared students) are:
(M,P), (M,C), (P,C), (P,H), (C,H), (H,B), (B,E).
Model as a graph and find a coloring with few time slots; interpret each color class as a set of exams that can be scheduled together.
Step 1: Build the conflict graph G.
Vertices are the exams.
Edges are exactly the listed conflict pairs.
A time slot assignment is a proper coloring c: V → {1..k}.
Step 2: Identify an obvious clique lower bound.
{M,P,C} form a triangle because edges (M,P), (M,C), (P,C) all exist.
So ω(G) ≥ 3 ⇒ χ(G) ≥ 3.
At least 3 time slots are necessary.
Step 3: Construct a 3-coloring.
Let’s try:
Color 1: P
Then M cannot be 1 (edge M–P) ⇒ set M=2.
C conflicts with P and M ⇒ cannot be 1 or 2 ⇒ set C=3.
H conflicts with P and C ⇒ cannot be 1 or 3 ⇒ set H=2.
B conflicts with H ⇒ cannot be 2 ⇒ set B=1.
E conflicts with B ⇒ cannot be 1 ⇒ set E=2 (or 3).
So one valid coloring is:
P=1, M=2, C=3, H=2, B=1, E=2.
Step 4: Read off the time slots as color classes.
Slot 1: {P, B}
Slot 2: {M, H, E}
Slot 3: {C}
Verify quickly: no conflicts within each slot because edges only connect different colors.
Insight: The independent-set view is exactly the scheduling interpretation: each time slot is an independent set of exams (no pair in conflict). Coloring is not just labeling—it’s partitioning into compatible batches.
A proper vertex coloring assigns colors so every edge connects differently colored vertices.
The chromatic number χ(G) is the minimum number of colors needed; it’s easy to verify a coloring, hard to find the minimum in general.
A k-coloring is equivalent to partitioning V into k independent sets (color classes).
Lower bounds: χ(G) ≥ ω(G) (clique number) and χ(G) ≥ ⌈|V| / α(G)⌉ (independent-set size bound).
Upper bounds: greedy coloring gives a constructive bound; universally χ(G) ≤ Δ(G) + 1, and often χ(G) ≤ Δ(G) (Brooks’ theorem exceptions aside).
2-coloring is exactly bipartiteness and is solvable via BFS/DFS; 3-coloring is NP-complete.
Practical coloring relies on heuristics (good orderings, DSATUR) and exploiting special graph structure (interval/chordal/planar).
Confusing χ(G) (minimum colors) with “colors used by my greedy run” (an upper bound that can be non-optimal).
Assuming χ(G) = Δ(G) + 1 always; many graphs need far fewer colors (even when Δ is large).
Forgetting the partition view: a color class must be an independent set; if you see an edge inside a class, the coloring is invalid.
Mixing up vertex coloring with edge coloring (a different problem with different theorems and bounds).
Show that for any graph G, χ(G) ≥ ω(G). Then give a graph where the inequality is strict (χ(G) > ω(G)).
Hint: In a clique, every pair of vertices is adjacent. For strictness, think of an odd cycle.
Proof: Let K be a clique of size ω(G). In a proper coloring, adjacent vertices must have different colors. Since every pair in K is adjacent, all vertices in K must have distinct colors, requiring at least ω(G) colors. Hence χ(G) ≥ ω(G).
Strict example: G = C₅. Then ω(C₅)=2 (no triangle), but χ(C₅)=3 because odd cycles are not 2-colorable.
Let G be a graph with |V| = 20 and α(G) = 5. Prove that χ(G) ≥ 4 using the independent-set bound. Is it possible that χ(G) = 4? Briefly justify.
Hint: Use k·α(G) ≥ |V| for k color classes that are independent sets.
Each color class is an independent set, so it has size ≤ α(G)=5. If G is k-colored, then the k color classes cover all vertices:
|V| ≤ ∑ᵢ |Cᵢ| ≤ ∑ᵢ α(G) = k·α(G).
So k ≥ |V|/α(G) = 20/5 = 4.
Thus χ(G) ≥ ⌈4⌉ = 4.
Yes, χ(G) could equal 4 if there exists a partition of V into 4 independent sets of size 5 (or smaller). The bound does not guarantee existence; it only rules out needing fewer than 4 colors.
You are given a graph G and an integer k = 2. Design an algorithm using BFS/DFS that either returns a valid 2-coloring or returns an odd cycle as a certificate that 2-coloring is impossible.
Hint: Use BFS layers (distance parity). When you find an edge connecting same-parity vertices, trace parents to extract a cycle.
Algorithm sketch:
1) Initialize color[v] = UNCOLORED and parent[v] = NIL.
2) For each component: pick an uncolored start s, set color[s]=0, run BFS.
3) When exploring edge (u,v):
Odd cycle extraction:
If color[u]=color[v], then u and v have the same parity distance from s in the BFS tree. Let P(u) be the path from u to the root via parent pointers, and P(v) similarly. Find their lowest common ancestor x by marking ancestors of u and walking up from v until you hit a mark. Then the cycle is:
(u → … → x) + (x → … → v) + edge (v,u).
Because both tree paths from x to u and x to v have the same parity, their lengths have the same parity, so the total cycle length is odd.
If BFS finishes with no conflict edges, the coloring is valid and is a proper 2-coloring.
Prereqs you’re using here: NP-Completeness, Graph Traversal: BFS and DFS
Next nodes that commonly follow coloring: