Your university has to schedule six exams. Some students take both DS and OS, so those two exams cannot be in the same slot. What is the smallest number of time slots that avoids every clash? A compiler has 20 variables but only 8 CPU registers: which variables can share a register? A telecom company must give radio frequencies to towers so that nearby towers never share one. All three are the same problem: graph coloring.
We draw a vertex for each exam (variable, tower) and an edge between two that conflict. Then we give each vertex a "color" (a slot, register or frequency) so that the two ends of every edge get different colors, using as few colors as possible. This chapter covers the chromatic number, the bounds and theorems that control it, the greedy algorithm, the chromatic polynomial (a counting tool that GATE loves), and edge coloring. We use the planarity results from Planar Graphs to prove a six-color theorem.
A proper vertex coloring of a graph G assigns a color to each vertex so that adjacent vertices get different colors. G is k-colorable if a proper coloring with at most k colors exists. The chromatic number χ(G) is the smallest such k.
All chromatic numbers and polynomials in this chapter were checked by computer (exhaustive search and deletion–contraction).
Chromatic Numbers of Standard Graphs
To prove χ(G) = k you always need two things: a coloring with k colors (upper bound) and a reason k − 1 colors are impossible (lower bound).
Graph | χ | Why |
|---|---|---|
Graph with no edges (n ≥ 1) | 1 | Nothing to conflict |
Complete graph Kn | n | Every pair is adjacent, so all colors differ |
Tree or path with ≥ 2 vertices | 2 | Color by parity of distance from a root |
Even cycle C2m | 2 | Alternate two colors around the cycle |
Odd cycle C2m+1 | 3 | Alternating fails when you return to the start |
Bipartite graph with ≥ 1 edge, e.g. Km,n | 2 | One color per side |
Wheel: hub + cycle of n rim vertices | 3 if n even, 4 if n odd | Rim needs χ(Cn) colors, hub needs one more |
Petersen graph | 3 | Has 5-cycles (≥ 3); a 3-coloring exists (Brooks, below) |
The 2-colorable graphs
Theorem (König). A graph is 2-colorable (bipartite) if and only if it has no cycle of odd length.
Proof. (⇒) In a 2-coloring, colors alternate along any cycle, so returning to the start takes an even number of steps. (⇐) Work on each component separately. Pick a vertex r and color every vertex by the parity of its distance d(r, x): even → red, odd → blue. Suppose an edge xy joined two vertices of the same parity. Then the shortest path r…x, the edge xy, and the shortest path y…r form a closed walk of length d(r, x) + 1 + d(r, y), which is odd. Any closed walk of odd length contains an odd cycle, a contradiction. ∎
This proof is also an algorithm: run BFS and check whether any edge joins two vertices of the same BFS level parity. So 2-colorability is decidable in O(V + E) time. In sharp contrast, deciding whether a graph is 3-colorable is NP-complete, even for planar graphs of maximum degree 4. There is no known efficient algorithm for χ(G) in general.
Bounds on χ(G)
Lower bounds
Clique bound: χ(G) ≥ ω(G), the size of the largest clique (complete subgraph). A triangle forces 3 colors.
Independence bound: χ(G) ≥ n / α(G), where α(G) is the size of the largest independent set (set of pairwise non-adjacent vertices). Each color class is an independent set, so k colors cover at most k·α(G) vertices.
The clique bound is not always tight. C5 has ω = 2 but χ = 3. There are even triangle-free graphs with arbitrarily large chromatic number (Mycielski's construction; the smallest triangle-free 4-chromatic graph, the Grötzsch graph, has 11 vertices). For the Petersen graph, α = 4 and n = 10, so the independence bound gives χ ≥ 10/4 = 2.5, that is χ ≥ 3.
Upper bounds
χ(G) ≤ Δ(G) + 1, where Δ(G) is the maximum degree.
Proof. Color the vertices one at a time in any order. When a vertex is reached, at most Δ of its neighbours are already colored, so at least one of Δ + 1 colors is free. ∎
Brooks' theorem (1941). If G is connected and is neither a complete graph nor an odd cycle, then χ(G) ≤ Δ(G).
So complete graphs and odd cycles are the only connected graphs that need Δ + 1 colors. For the Petersen graph, Δ = 3, so χ ≤ 3, and together with the lower bound, χ = 3 exactly.
The Greedy Algorithm
The proof of χ ≤ Δ + 1 is an algorithm:
Greedy coloring (colors are 0, 1, 2, ...)
for each vertex v in some chosen order:
give v the smallest color not used by any already-colored neighbour
Greedy is fast (O(V + E)) but its result depends on the order, and it does not always find χ(G). A popular heuristic is the Welsh–Powell order: color vertices in decreasing order of degree, since high-degree vertices are the hardest to fit in later.
Worked example: exam timetable
Six exams; an edge means some student takes both:
Conflicts: DS–OS, DS–DBMS, OS–DBMS, OS–CN, DBMS–CN,
CN–TOC, TOC–DM, DM–DS, DM–OS
Degrees: OS 4, DS 3, DBMS 3, CN 3, DM 3, TOC 2
Welsh–Powell order: OS, DS, DBMS, CN, DM, TOC.
Step | Vertex | Colors of colored neighbours | Color given |
|---|---|---|---|
1 | OS | none | 0 |
2 | DS | OS = 0 | 1 |
3 | DBMS | DS = 1, OS = 0 | 2 |
4 | CN | OS = 0, DBMS = 2 | 1 |
5 | DM | DS = 1, OS = 0 | 2 |
6 | TOC | CN = 1, DM = 2 | 0 |
Three slots: {OS, TOC}, {DS, CN}, {DBMS, DM}. Is this optimal? Yes: DS, OS and DBMS form a triangle, so at least 3 slots are needed. Upper bound 3 (the schedule) = lower bound 3 (the triangle), so χ = 3.
When greedy goes wrong
Take the crown graph: vertices u1, …, un and v1, …, vn, with ui adjacent to vj whenever i ≠ j. It is bipartite, so χ = 2. But in the order u1, v1, u2, v2, … greedy gives ui and vi color i − 1 (each sees colors 0 … i − 2 already on its neighbours) and ends up using n colors. A bad order can be arbitrarily bad. (On the other hand, for every graph some order makes greedy optimal: list the vertices color class by color class of an optimal coloring.)
Coloring Planar Graphs
Coloring started with maps: color the countries so that countries sharing a border get different colors. Put a vertex in each country and join neighbours (this is the dual graph from Planar Graphs), and map coloring becomes vertex coloring of a planar graph.
Four Color Theorem. Every planar graph is 4-colorable.
Conjectured in 1852, it was proved by Appel and Haken in 1976 with heavy computer checking, the first major theorem proved that way. Robertson, Sanders, Seymour and Thomas gave a simpler (still computer-assisted) proof in 1997, and Gonthier verified a proof completely in the Coq proof assistant in 2005. The bound 4 is tight, since K4 is planar.
A weaker result has a short proof that uses only Euler's formula:
Six Color Theorem. Every simple planar graph is 6-colorable.
Proof. Induction on the number of vertices n. A graph with at most 6 vertices is trivially 6-colorable. Let G be simple and planar with n > 6 vertices. By the corollary in Planar Graphs, G has a vertex v of degree at most 5. The graph G − v is simple and planar with n − 1 vertices, so by the induction hypothesis it has a 6-coloring. Put v back: its at most 5 neighbours use at most 5 colors, so a sixth color is free for v. ∎
Heawood (1890) improved this to a Five Color Theorem with a cleverer argument at the degree-5 vertex (swapping colors along two-colored paths). Going from 5 to 4 is what needed the computer.
The Chromatic Polynomial
The chromatic polynomial P(G, k) is the number of proper colorings of G using colors from a set of k colors. Then χ(G) is the smallest positive integer k with P(G, k) > 0.
Note that colorings are counted with the colors labelled: swapping red and blue gives a different coloring. Basic formulas, by the multiplication principle from Counting Principles:
Empty graph on n vertices: P = kn.
Kn: P = k(k − 1)(k − 2)⋯(k − n + 1), since each new vertex must avoid all previous colors.
Any tree on n vertices: P = k(k − 1)n − 1. Color the root in k ways; each other vertex, taken in BFS order, only has to avoid its parent's color.
Cycle Cn: P = (k − 1)n + (−1)n(k − 1).
Deletion–contraction
For any edge e = uv: P(G, k) = P(G − e, k) − P(G / e, k), where G − e deletes the edge and G / e merges u and v into one vertex (removing duplicate edges).
Why it works. Colorings of G − e split into two kinds: those where u and v get different colors (exactly the proper colorings of G) and those where they get the same color (exactly the proper colorings of G / e). So P(G − e) = P(G) + P(G / e). ∎
Worked example: the diamond (K4 minus an edge)
Let G = K4 and let e be any edge. Then G − e is the diamond D, and G / e is K3. Rearranging the identity, P(D) = P(K4) + P(K3):
P(D, k) = k(k−1)(k−2)(k−3) + k(k−1)(k−2)
= k(k−1)(k−2)[(k−3) + 1]
= k(k−1)(k−2)²
k = 2: 2·1·0·0 = 0
k = 3: 3·2·1·1 = 6
k = 4: 4·3·2·2 = 48
Since P(D, 2) = 0 and P(D, 3) = 6 > 0, χ(D) = 3.
Direct check of P(D, 3) = 6: the two degree-3 vertices (the edge shared by both triangles) take 2 different colors in 3 × 2 ways, and then each of the other two vertices is forced to the third color. 3 × 2 × 1 × 1 = 6. ✓
Worked example: C4
P(C4, k) = (k − 1)4 + (k − 1) = k4 − 4k3 + 6k2 − 3k. With 3 colors: 24 + 2 = 18 colorings.
Properties worth remembering
P(G, k) has degree n (number of vertices) and leading coefficient 1.
The coefficient of kn − 1 is −e (minus the number of edges). For C4: −4. ✓
For a graph with at least one vertex the constant term is 0 (no colorings with 0 colors), and the coefficients alternate in sign: + for kn, − for kn − 1, and so on, with some of the lowest ones equal to 0 (for C4: +1, −4, +6, −3, 0).
If G has components G1, G2, then P(G) = P(G1)·P(G2).
Edge Coloring
A proper edge coloring gives colors to edges so that edges sharing an endpoint get different colors. The minimum number of colors is the chromatic index χ′(G).
Each color class is a matching, so edge coloring models scheduling where each "match" uses two resources at once: a round-robin tournament (each round, a team plays at most once) or data transfers between pairs of machines.
Obviously χ′(G) ≥ Δ(G), since the Δ edges at a max-degree vertex all meet.
Vizing's theorem: for a simple graph, χ′(G) is either Δ or Δ + 1.
König's edge-coloring theorem: for a bipartite graph, χ′(G) = Δ.
χ′(Kn) = n − 1 if n is even, n if n is odd. (A round-robin among 8 teams needs 7 rounds; among 7 teams, 7 rounds with one team resting each round.)
The Petersen graph has Δ = 3 but χ′ = 4.
Checking with Code
Greedy coloring, an exact backtracking search for χ, and a brute-force counter that checks the chromatic polynomial of C4.
def greedy_coloring(graph, order):
"""Give each vertex (in the given order) the smallest color not used by a neighbour."""
color = {}
for v in order:
used = {color[u] for u in graph[v] if u in color}
c = 0
while c in used:
c += 1
color[v] = c
return color
def chromatic_number(graph):
"""Exact chi(G) by backtracking: try k = 1, 2, 3, ... colors."""
vertices = list(graph)
def can_color(k, i, color):
if i == len(vertices):
return True
v = vertices[i]
for c in range(k):
if all(color.get(u) != c for u in graph[v]):
color[v] = c
if can_color(k, i + 1, color):
return True
del color[v]
return False
k = 1
while not can_color(k, 0, {}):
k += 1
return k
def count_colorings(graph, k):
"""Number of proper colorings with at most k colors = P(G, k)."""
vertices = list(graph)
def count(i, color):
if i == len(vertices):
return 1
v, total = vertices[i], 0
for c in range(k):
if all(color.get(u) != c for u in graph[v]):
color[v] = c
total += count(i + 1, color)
del color[v]
return total
return count(0, {})
def make_graph(edges):
g = {}
for a, b in edges:
g.setdefault(a, set()).add(b)
g.setdefault(b, set()).add(a)
return g
# Exam timetable: an edge means some student takes both courses
exams = make_graph([("DS", "OS"), ("DS", "DBMS"), ("OS", "DBMS"), ("OS", "CN"),
("DBMS", "CN"), ("CN", "TOC"), ("TOC", "DM"), ("DM", "DS"), ("DM", "OS")])
order = sorted(exams, key=lambda v: -len(exams[v])) # Welsh-Powell: largest degree first
print("Welsh-Powell order:", order)
print("Greedy slots:", greedy_coloring(exams, order))
print("Minimum slots chi =", chromatic_number(exams))
# Crown graph: u_i joined to v_j for every i != j (bipartite, so chi = 2)
n = 4
crown = make_graph([(f"u{i}", f"v{j}") for i in range(n) for j in range(n) if i != j])
bad = [x for i in range(n) for x in (f"u{i}", f"v{i}")] # u0, v0, u1, v1, ...
print("Crown graph: chi =", chromatic_number(crown),
"| greedy with bad order uses", max(greedy_coloring(crown, bad).values()) + 1, "colors")
# Chromatic polynomial check: C4 should give (k-1)^4 + (k-1)
c4 = make_graph([(1, 2), (2, 3), (3, 4), (4, 1)])
for k in range(1, 5):
print(f"P(C4, {k}) = {count_colorings(c4, k):3} formula = {(k-1)**4 + (k-1)}")
Output:
Welsh-Powell order: ['OS', 'DS', 'DBMS', 'CN', 'DM', 'TOC']
Greedy slots: {'OS': 0, 'DS': 1, 'DBMS': 2, 'CN': 1, 'DM': 2, 'TOC': 0}
Minimum slots chi = 3
Crown graph: chi = 2 | greedy with bad order uses 4 colors
P(C4, 1) = 0 formula = 0
P(C4, 2) = 2 formula = 2
P(C4, 3) = 18 formula = 18
P(C4, 4) = 84 formula = 84
The exact search tries every possibility, so it takes exponential time in the worst case. That is expected: computing χ(G) is NP-hard.
Common Mistakes
Showing only an upper bound. A 3-coloring shows χ ≤ 3. To claim χ = 3 you must also show 2 colors fail (an odd cycle, a triangle, …).
Assuming χ = ω. The largest clique is only a lower bound; C5 has ω = 2 and χ = 3.
Trusting greedy as optimal. Greedy gives an upper bound that depends on the order.
Confusing χ and χ′. Vertex coloring and edge coloring are different problems; χ′(K4) = 3 but χ(K4) = 4.
Counting unlabelled colorings. P(G, k) counts colorings with named colors, so P(K2, 2) = 2, not 1.
Wheel convention. Books disagree on whether Wn has n vertices in total or n rim vertices. Reason from the rim cycle: even rim → 3 colors, odd rim → 4.
Practice and GATE-Style Questions
Q1. How many proper colorings of a path on 5 vertices use at most 3 colors?
A path is a tree: P = k(k − 1)4 = 3 × 24 = 48.
Q2. Find the number of proper 3-colorings of C5 and C6.
(k − 1)n + (−1)n(k − 1) with k = 3: C5: 32 − 2 = 30; C6: 64 + 2 = 66.
Q3. What is the chromatic number of a wheel with 7 rim vertices? With 8?
7 rim vertices form an odd cycle needing 3 colors, plus 1 for the hub (adjacent to all rim vertices): 4. With 8: even cycle needs 2, plus the hub: 3.
Q4. A graph has chromatic polynomial k4 − 4k3 + 6k2 − 3k. How many vertices and edges does it have, and what is χ?
Degree 4 → 4 vertices; coefficient of k3 is −4 → 4 edges. P(1) = 1 − 4 + 6 − 3 = 0, P(2) = 16 − 32 + 24 − 6 = 2 > 0, so χ = 2. (It is C4.)
Q5. In a tournament where 10 teams each play every other team once, and a team plays at most one match per day, what is the minimum number of days?
This is χ′(K10). Since 10 is even, χ′ = n − 1 = 9 days.
Q6. Interview: how would you check whether a graph is bipartite?
BFS (or DFS) from each uncolored vertex, giving neighbours the opposite color. If you ever find an edge whose ends have the same color, there is an odd cycle and the graph is not bipartite. O(V + E) time.
Summary
χ(G) is the fewest colors in a proper vertex coloring. Proving χ = k needs a k-coloring plus a proof that k − 1 colors fail.
Bipartite ⇔ 2-colorable ⇔ no odd cycle (checkable by BFS). 3-colorability is NP-complete.
ω(G) ≤ χ(G) ≤ Δ(G) + 1; Brooks: χ ≤ Δ unless complete or odd cycle; also χ ≥ n/α.
Greedy is fast but order-dependent; Welsh–Powell colors high degrees first.
Planar graphs: 6-colorable by an easy induction, 5 by Heawood, 4 by the Four Color Theorem.
P(G, k): kn (empty), k(k − 1)…(k − n + 1) (Kn), k(k − 1)n − 1 (trees), (k − 1)n + (−1)n(k − 1) (cycles); P(G) = P(G − e) − P(G / e).
Edge coloring: Δ ≤ χ′ ≤ Δ + 1 (Vizing); χ′ = Δ for bipartite graphs.
Coloring is conflict resolution: vertices are tasks, edges are clashes, and colors are the resources. The chromatic number is the least amount of resource that removes every clash.