← 🕸️ Graph Theory
Subtopic 6 of 7

4.6Colouring, cliques and independent sets

The idea

A proper colouring gives adjacent vertices different colours; the least number of colours is the chromatic number χ. A clique is a set of mutually adjacent vertices and an independent set has no adjacent pair.

Think of it like this: Scheduling exams: a clash is an edge, a colour is a time slot, and χ is the fewest slots you need.

Why it exists

Chromatic-number questions mix bipartite tests, odd cycles and clique bounds.

How it works

  1. ω ≤ χ ≤ Δ + 1. A clique of size k needs k colours.
  2. Bipartite ⇔ no odd cycle ⇔ χ ≤ 2. Trees have χ = 2.
  3. χ(K_n) = n, χ(C_odd) = 3, χ(C_even) = 2, every planar graph has χ ≤ 4.
  4. α · χ ≥ n; the complement of a clique is an independent set.

Worked example: The Petersen graph

It has no triangle, so ω = 2, but it has 5-cycles, so it is not bipartite: χ = 3.

Now play with it

  • →Load C₅: it needs 3 colours although ω = 2.
  • →Load K₃,₃: it needs only 2.
12345678910
✗ not bipartite (has an odd cycle)
Chromatic number χ (vertex colours shown)3
Largest clique ω2: {1,2}
Largest independent set α4: {3,5,6,7}
Boundsω ≤ χ ≤ Δ+1 = 4
Alsoα · χ ≥ n: 12 ≥ 10

Check yourself

The chromatic number of a cycle with 7 vertices is

Remember: ω ≤ χ ≤ Δ+1. Odd cycle ⇒ χ ≥ 3. Bipartite ⇔ χ ≤ 2.
Exam notes (the dense version)

The chromatic number χ(G) is the fewest colours giving adjacent vertices different colours. χ ≥ ω (clique), χ ≤ Δ + 1, and for bipartite graphs χ = 2 (no odd cycle). χ(K_n) = n; χ(C_odd) = 3; χ(C_even) = 2; every tree has χ = 2; every planar graph has χ ≤ 4 (Four Colour Theorem). α(G) is the largest independent set; α·χ ≥ n. The complement turns cliques into independent sets.

Previous year questions: Graph Theory (24)

PYQs are grouped by topic, so this is the full set for Graph Theory; try the ones that match this subtopic. Open all 24 on the topic page.