Complexity Atlas
HE
one new vertex joined to everything

3COL ≤p 4COL

3COL≤p4COL\mathrm{3COL}\le_p\mathrm{4COL}, hence 4COL\mathrm{4COL} is NP-complete. The same idea gives 3COL≤pkCOL\mathrm{3COL}\le_p k\mathrm{COL} for every constant k≥3k\ge3.

The construction

On input G=(V,E)G=(V,E):

  1. Build G^\hat G by adding a new vertex v^\hat v and joining it to every vertex of VV.
  2. Return G^\hat G.

In general, for kCOLk\mathrm{COL}: add k−3k-3 new vertices, join them pairwise (a clique) and join each to every vertex of VV.

The vertex v^\hat v "burns" the fourth colour: it is adjacent to every original vertex, so no original vertex can take its colour.

Visualization

Guided construction

3-Colouring → 4-Colouring

Step 1 of 7
3-colouring to 4-colouring: adding one universally joined vertexThe left panel shows the input graph with a colouring; the right panel shows the same graph plus a new vertex joined to every original vertex, with its colouring. Later steps swap the input for K₄ and compare the identity map, an isolated extra vertex and the real construction.Input instance of 3COLG = C₅v₁1v₂2v₃1v₄2v₅3C₅ ∈ 3COL ✓
edge of G (kept)colour 1 (dashed)colour 2 (solid)colour 3 (dotted)

Correctness — both directions

3COL ∈ ⟹ 4COL ∈

Suppose G∈3COLG\in\mathrm{3COL}; take a legal f:V→{1,2,3}f:V\to\{1,2,3\}. Define g:V^→{1,2,3,4}g:\hat V\to\{1,2,3,4\} by g(v)={f(v)v∈V4otherwiseg(v)=\begin{cases} f(v) & v\in V\\ 4 & \text{otherwise}\end{cases} Let e=xy∈E^e=xy\in\hat E.

  • If e∈Ee\in E: then g(x)=f(x)g(x)=f(x), g(y)=f(y)g(y)=f(y), and legality of ff in GG gives g(x)≠g(y)g(x)\ne g(y).
  • Otherwise ee is a new edge, so x=v^x=\hat v or y=v^y=\hat v. Then v^\hat v has colour 44 and the other has a colour in {1,2,3}\{1,2,3\}, so again g(x)≠g(y)g(x)\ne g(y).

So gg is a legal 4-colouring, i.e. G^∈4COL\hat G\in\mathrm{4COL}.

4COL ∈ ⟹ 3COL ∈

Suppose G^∈4COL\hat G\in\mathrm{4COL}; take a legal g:V^→{1,2,3,4}g:\hat V\to\{1,2,3,4\}. W.l.o.g. g(v^)=4g(\hat v)=4 — colours are perfectly symmetric, and if v^\hat v got another colour, rename the two.

Define f(v)=g(v)f(v)=g(v) for v∈Vv\in V, and check the range really is {1,2,3}\{1,2,3\}: let x∈Vx\in V. Since v^\hat v was joined to every vertex of VV, we have xv^∈E^x\hat v\in\hat E, so g(x)≠g(v^)=4g(x)\ne g(\hat v)=4. Hence f(x)∈{1,2,3}f(x)\in\{1,2,3\} for every x∈Vx\in V.

Now let xy∈Exy\in E. No edge was removed, so xy∈E^xy\in\hat E too, and legality of gg in G^\hat G gives f(x)=g(x)≠g(y)=f(y)f(x)=g(x)\ne g(y)=f(y). So ff is a legal 3-colouring of GG, i.e. G∈3COLG\in\mathrm{3COL}.

Cost of the reduction

TimeO(|V| + |E|)
SpaceO(|V| + |E|)
Output size|V| + 1 vertices, |E| + |V| edges

The construction adds one vertex and ∣V∣|V| edges, so it is linear in the input size. The output exceeds the input by less than a factor of two plus a constant.

What it buys

4COL\mathrm{4COL} is NP-complete. With 2COL∈P\mathrm{2COL}\in\mathrm P the picture is complete: k=2k=2 easy, k≥3k\ge3 hard — a sharp jump at exactly one place.

Pitfalls

  • The identity fails. If GG is 33-colourable it is in particular 44-colourable — the first direction works, which is exactly why one should be suspicious. The second collapses: K4K_4 is 44-colourable and certainly not 33-colourable, so K4∈4COLK_4\in\mathrm{4COL} but K4∉3COLK_4\notin\mathrm{3COL}.

  • A new vertex with no edges is not enough. The step "for every x∈Vx\in V, g(x)≠4g(x)\ne4" rests entirely on the edge xv^x\hat v existing. Without those edges nothing stops a vertex of VV from taking colour 44. Counterexample: K4K_4 plus an isolated vertex is 44-colourable, while K4K_4 is not 33-colourable.

  • "Add a new vertex and colour it with a fourth colour" is a serious misstatement. The construction is the same, but the phrasing grants the algorithm access to a colouring. A reduction algorithm has — and can have — no access to a solution: it takes a graph and returns a graph. The colourings ff and gg appear only in the correctness proof, where, and only where, "a legal colouring exists" may be assumed.

The chain

Where this was read from

  • Lesson 11משפט 2: 4COL\mathrm{4COL} היא NP-complete
  • Lesson 10הרחבה (מוכחת בשיעור 11): 3COL≤p4COL\mathrm{3COL} \le_p \mathrm{4COL}