graph coloring

Picture colouring a map so that no two countries sharing a border get the same colour. Now generalise: vertices are countries and edges are shared borders, and you want to colour the vertices so that adjacent ones always differ. Graph colouring asks: can the graph be coloured with at most k colours? It directly models conflict-avoidance, such as assigning exam timeslots so that no student has two exams at once.

Formally, a proper k-colouring of a graph G assigns one of k colours to each vertex so that no edge joins two vertices of the same colour. The decision problem k-COLORING takes G and a number k and asks whether such a colouring exists. It is in NP: a colouring is the certificate, and a verifier checks every edge in polynomial time to confirm its two endpoints differ in colour. The smallest number of colours that works is called the chromatic number of G.

Here the threshold is sharp and surprising. 2-COLORING is in P: a graph is 2-colourable if and only if it is bipartite, which you can test in linear time by a breadth-first scan. But 3-COLORING is NP-complete, proven by a gadget reduction from 3-SAT. So colourability is easy with two colours and hard with three, the same two-to-three jump we saw with SAT. Even the famous Four Colour Theorem (every planar map needs at most four colours) does not rescue us: deciding whether a general graph is 3-colourable stays NP-complete, and even 3-colouring planar graphs is NP-complete. Colouring is a workhorse model for scheduling, register allocation in compilers, and frequency assignment.