41.03Intermediate / Advanced5 topics18 min4 interactive animations

Graph coloring

Colouring assigns colours to vertices so that no edge joins two equal colours. Two colours are decided by BFS, but the general chromatic number is NP-hard, so practice relies on greedy rules, DSATUR and exact search for small graphs.

Learning goals

Test 2-colourability with BFS
Write a greedy colouring and explain its dependence on vertex order
Use DSATUR for better colourings
Find the exact chromatic number by backtracking and know its complexity

Prerequisites

BFS (Chapter 33)Backtracking (Chapter 24)

Scheduling exams so that no student has two at once, assigning radio frequencies to nearby towers, allocating registers in a compiler: each is a graph colouring problem. Conflicts are edges, colours are time slots, frequencies or registers, and fewer colours mean a cheaper solution.

41.03.1

Bipartite 2-coloring

A **proper colouring** gives each vertex a colour so that adjacent vertices differ. The smallest number of colours is the **chromatic number** χ(G). A graph is 2-colourable exactly when it is **bipartite**, and that is the one case that is easy: it has no odd cycle.

Run a BFS from every unvisited vertex, giving the start colour 0 and each newly found neighbour the opposite colour. If some edge joins two vertices with the same colour, the BFS tree paths together with that edge form an odd cycle, and no 2-colouring exists. Otherwise the two colour classes are the two sides. The code returns the colouring or null, in O(V + E).

In the animation choose the first method. The “crown” graph (vertices 0 to 5, edges 0-3, 0-5, 2-1, 2-5, 4-1, 4-3) is bipartite with sides {0, 2, 4} and {1, 3, 5}; the BFS finds them. On the triangle preset the BFS stops at edge 1-2, where both ends have colour 1, and reports an odd cycle.

Java

1@SuppressWarnings("unchecked")
2static List<Integer>[] adjacency(int n, int[][] edges) {
3    List<Integer>[] adj = new List[n];
4    for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
5    for (int[] e : edges) { adj[e[0]].add(e[1]); adj[e[1]].add(e[0]); }
6    return adj;
7}
8static int[] bipartiteColouring(int n, List<Integer>[] adj) {         // 2-colouring by BFS, or null when an odd cycle exists
9    int[] colour = new int[n];
10    Arrays.fill(colour, -1);
11    for (int s = 0; s < n; s++) {
12        if (colour[s] != -1) continue;
13        colour[s] = 0;
14        Deque<Integer> queue = new ArrayDeque<>(List.of(s));
15        while (!queue.isEmpty()) {
16            int u = queue.poll();
17            for (int v : adj[u]) {
18                if (colour[v] == colour[u]) return null;              // both ends of an edge got the same colour
19                if (colour[v] == -1) { colour[v] = 1 - colour[u]; queue.add(v); }
20            }
21        }
22    }
23    return colour;
24}

Worst

O(V + E)

Space

O(V)

Graph colouring: 2-colouring, greedy, DSATUR and the exact chromatic number

Interactive · edit the input

undirected graph · 6 vertices · 6 edges

Colour 0Colour 1Colour 2Colour 3Vertex being coloured

colour of each vertex

–0

–1

–2

–3

–4

–5

Setup

Greedy colouring: take the vertices in index order and give each the smallest colour that none of its already coloured neighbours uses. It never needs more than (maximum degree + 1) colours, but the order decides how many it really uses.

Step 1 / 8

Java

1@SuppressWarnings("unchecked")
2static List<Integer>[] adjacency(int n, int[][] edges) {
3    List<Integer>[] adj = new List[n];
4    for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
5    for (int[] e : edges) { adj[e[0]].add(e[1]); adj[e[1]].add(e[0]); }
6    return adj;
7}
8static int[] bipartiteColouring(int n, List<Integer>[] adj) {         // 2-colouring by BFS, or null when an odd cycle exists
9    int[] colour = new int[n];
10    Arrays.fill(colour, -1);
11    for (int s = 0; s < n; s++) {
12        if (colour[s] != -1) continue;
13        colour[s] = 0;
14        Deque<Integer> queue = new ArrayDeque<>(List.of(s));
15        while (!queue.isEmpty()) {
16            int u = queue.poll();
17            for (int v : adj[u]) {
18                if (colour[v] == colour[u]) return null;              // both ends of an edge got the same colour
19                if (colour[v] == -1) { colour[v] = 1 - colour[u]; queue.add(v); }
20            }
21        }
22    }
23    return colour;
24}
25static int[] greedyColouring(int n, List<Integer>[] adj) {            // vertices in index order, smallest free colour
26    int[] colour = new int[n];
27    Arrays.fill(colour, -1);
28    for (int v = 0; v < n; v++) {
29        boolean[] taken = new boolean[n + 1];
30        for (int u : adj[v]) if (colour[u] != -1) taken[colour[u]] = true;
31        int c = 0;
32        while (taken[c]) c++;
33        colour[v] = c;
34    }
35    return colour;
36}
37static int[] dsatur(int n, List<Integer>[] adj) {                     // always colour the most constrained vertex next
38    int[] colour = new int[n];
39    Arrays.fill(colour, -1);
40    for (int step = 0; step < n; step++) {
41        int pick = -1, bestSat = -1;
42        for (int v = 0; v < n; v++) {
43            if (colour[v] != -1) continue;
44            Set<Integer> seen = new HashSet<>();                      // saturation: distinct colours among neighbours
45            for (int u : adj[v]) if (colour[u] != -1) seen.add(colour[u]);
46            if (seen.size() > bestSat || (seen.size() == bestSat && adj[v].size() > adj[pick].size())) { pick = v; bestSat = seen.size(); }
47        }
48        boolean[] taken = new boolean[n + 1];
49        for (int u : adj[pick]) if (colour[u] != -1) taken[colour[u]] = true;
50        int c = 0;
51        while (taken[c]) c++;
52        colour[pick] = c;
53    }
54    return colour;
55}
56static boolean tryColour(int v, int k, int[] colour, List<Integer>[] adj, int used) {
57    if (v == colour.length) return true;
58    for (int c = 0; c < k && c <= used; c++) {                        // c <= used: never open a colour before the one below it
59        boolean ok = true;
60        for (int u : adj[v]) if (u < v && colour[u] == c) ok = false;
61        if (!ok) continue;
62        colour[v] = c;
63        if (tryColour(v + 1, k, colour, adj, Math.max(used, c + 1))) return true;
64    }
65    colour[v] = -1;
66    return false;
67}
68static int chromaticNumber(int n, List<Integer>[] adj) {              // smallest k that admits a proper k-colouring
69    for (int k = 1; k <= n; k++) {
70        int[] colour = new int[n];
71        if (tryColour(0, k, colour, adj, 0)) return k;
72    }
73    return n;
74}

Live state

0 vertices coloured

edges

No condition evaluated on this step

Execution trace (dry run table)Show 8 steps

Step	Line	State	What happens
1	L25	n=6 edges=6	Greedy colouring: take the vertices in index order and give each the smallest colour that none of its already coloured neighbours uses. It never needs more than (maximum degree + 1) colours, but the order decides how many it really uses.
2	L33	vertex=0 colour=0 colours_used=1	Vertex 0: neighbours already use no colour, so the smallest free colour is 0.
3	L33	vertex=1 colour=0 colours_used=1	Vertex 1: neighbours already use no colour, so the smallest free colour is 0.
4	L33	vertex=2 colour=1 colours_used=2	Vertex 2: neighbours already use {0}, so the smallest free colour is 1.
5	L33	vertex=3 colour=1 colours_used=2	Vertex 3: neighbours already use {0}, so the smallest free colour is 1.
6	L33	vertex=4 colour=2 colours_used=3	Vertex 4: neighbours already use {0,1}, so the smallest free colour is 2.
7	L33	vertex=5 colour=2 colours_used=3	Vertex 5: neighbours already use {0,1}, so the smallest free colour is 2.
8	L35	return=3 colouring=0:0 1:0 2:1 3:1 4:2 5:2 proper=yes	3 colours used (greedy): 0:0 1:0 2:1 3:1 4:2 5:2. The colouring is proper, but it is only an upper bound on the chromatic number.

41.03.2

Greedy coloring

**Greedy colouring** takes the vertices in some order and gives each the smallest colour not used by its already-coloured neighbours. It runs in O(V + E) and uses at most Δ + 1 colours, where Δ is the maximum degree, because a vertex with d ≤ Δ neighbours always has a free colour among the first d + 1.

The order decides everything. Greedy is optimal for some order of the vertices, but a bad order can be far from optimal even on a bipartite graph. The crown graph shows it: in index order greedy gives vertices 0 and 1 colour 0, then 2 and 3 colour 1, then 4 and 5 colour 2, so it uses 3 colours although the graph is bipartite and 2 suffice. Run the second method to watch this.

A better order helps: colour high-degree vertices first (Welsh-Powell), or use the order produced by degeneracy (smallest-last), which guarantees at most degeneracy + 1 colours and is excellent on planar graphs (at most 6 colours).

Java

1static int[] greedyColouring(int n, List<Integer>[] adj) {            // vertices in index order, smallest free colour
2    int[] colour = new int[n];
3    Arrays.fill(colour, -1);
4    for (int v = 0; v < n; v++) {
5        boolean[] taken = new boolean[n + 1];
6        for (int u : adj[v]) if (colour[u] != -1) taken[colour[u]] = true;
7        int c = 0;
8        while (taken[c]) c++;
9        colour[v] = c;
10    }
11    return colour;
12}

Worst

O(V + E) (the code below is O(V · n) because of the boolean array per vertex)

Space

O(V)

Graph colouring: 2-colouring, greedy, DSATUR and the exact chromatic number

Interactive · edit the input

undirected graph · 6 vertices · 6 edges

Colour 0Colour 1Colour 2Colour 3Vertex being coloured

colour of each vertex

–0

–1

–2

–3

–4

–5

Setup

Step 1 / 8

Java

1@SuppressWarnings("unchecked")
2static List<Integer>[] adjacency(int n, int[][] edges) {
3    List<Integer>[] adj = new List[n];
4    for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
5    for (int[] e : edges) { adj[e[0]].add(e[1]); adj[e[1]].add(e[0]); }
6    return adj;
7}
8static int[] bipartiteColouring(int n, List<Integer>[] adj) {         // 2-colouring by BFS, or null when an odd cycle exists
9    int[] colour = new int[n];
10    Arrays.fill(colour, -1);
11    for (int s = 0; s < n; s++) {
12        if (colour[s] != -1) continue;
13        colour[s] = 0;
14        Deque<Integer> queue = new ArrayDeque<>(List.of(s));
15        while (!queue.isEmpty()) {
16            int u = queue.poll();
17            for (int v : adj[u]) {
18                if (colour[v] == colour[u]) return null;              // both ends of an edge got the same colour
19                if (colour[v] == -1) { colour[v] = 1 - colour[u]; queue.add(v); }
20            }
21        }
22    }
23    return colour;
24}
25static int[] greedyColouring(int n, List<Integer>[] adj) {            // vertices in index order, smallest free colour
26    int[] colour = new int[n];
27    Arrays.fill(colour, -1);
28    for (int v = 0; v < n; v++) {
29        boolean[] taken = new boolean[n + 1];
30        for (int u : adj[v]) if (colour[u] != -1) taken[colour[u]] = true;
31        int c = 0;
32        while (taken[c]) c++;
33        colour[v] = c;
34    }
35    return colour;
36}
37static int[] dsatur(int n, List<Integer>[] adj) {                     // always colour the most constrained vertex next
38    int[] colour = new int[n];
39    Arrays.fill(colour, -1);
40    for (int step = 0; step < n; step++) {
41        int pick = -1, bestSat = -1;
42        for (int v = 0; v < n; v++) {
43            if (colour[v] != -1) continue;
44            Set<Integer> seen = new HashSet<>();                      // saturation: distinct colours among neighbours
45            for (int u : adj[v]) if (colour[u] != -1) seen.add(colour[u]);
46            if (seen.size() > bestSat || (seen.size() == bestSat && adj[v].size() > adj[pick].size())) { pick = v; bestSat = seen.size(); }
47        }
48        boolean[] taken = new boolean[n + 1];
49        for (int u : adj[pick]) if (colour[u] != -1) taken[colour[u]] = true;
50        int c = 0;
51        while (taken[c]) c++;
52        colour[pick] = c;
53    }
54    return colour;
55}
56static boolean tryColour(int v, int k, int[] colour, List<Integer>[] adj, int used) {
57    if (v == colour.length) return true;
58    for (int c = 0; c < k && c <= used; c++) {                        // c <= used: never open a colour before the one below it
59        boolean ok = true;
60        for (int u : adj[v]) if (u < v && colour[u] == c) ok = false;
61        if (!ok) continue;
62        colour[v] = c;
63        if (tryColour(v + 1, k, colour, adj, Math.max(used, c + 1))) return true;
64    }
65    colour[v] = -1;
66    return false;
67}
68static int chromaticNumber(int n, List<Integer>[] adj) {              // smallest k that admits a proper k-colouring
69    for (int k = 1; k <= n; k++) {
70        int[] colour = new int[n];
71        if (tryColour(0, k, colour, adj, 0)) return k;
72    }
73    return n;
74}

Live state

0 vertices coloured

edges

No condition evaluated on this step

Execution trace (dry run table)Show 8 steps

Step	Line	State	What happens
1	L25	n=6 edges=6	Greedy colouring: take the vertices in index order and give each the smallest colour that none of its already coloured neighbours uses. It never needs more than (maximum degree + 1) colours, but the order decides how many it really uses.
2	L33	vertex=0 colour=0 colours_used=1	Vertex 0: neighbours already use no colour, so the smallest free colour is 0.
3	L33	vertex=1 colour=0 colours_used=1	Vertex 1: neighbours already use no colour, so the smallest free colour is 0.
4	L33	vertex=2 colour=1 colours_used=2	Vertex 2: neighbours already use {0}, so the smallest free colour is 1.
5	L33	vertex=3 colour=1 colours_used=2	Vertex 3: neighbours already use {0}, so the smallest free colour is 1.
6	L33	vertex=4 colour=2 colours_used=3	Vertex 4: neighbours already use {0,1}, so the smallest free colour is 2.
7	L33	vertex=5 colour=2 colours_used=3	Vertex 5: neighbours already use {0,1}, so the smallest free colour is 2.
8	L35	return=3 colouring=0:0 1:0 2:1 3:1 4:2 5:2 proper=yes	3 colours used (greedy): 0:0 1:0 2:1 3:1 4:2 5:2. The colouring is proper, but it is only an upper bound on the chromatic number.

41.03.3

Chromatic number

The **chromatic number** is found exactly by asking, for k = 1, 2, 3, …, whether a proper colouring with at most k colours exists, and stopping at the first success. For one k, backtracking assigns colours to the vertices in order and undoes a choice when a vertex has no allowed colour left.

The code uses a standard symmetry break: a vertex may open colour c only when colours 0 … c − 1 are already in use, so permuting colour names does not produce duplicate searches. The search is exponential in the worst case, which is expected: deciding whether χ(G) ≤ 3 is already NP-complete.

In the animation the third method colours the 5-cycle with one chord: k = 1 and k = 2 fail, and k = 3 succeeds (8 assignments, 5 backtracks). For the complete graph K4 every smaller k fails and χ = 4 (10 assignments, 9 backtracks). Lower bounds come from cliques (χ ≥ ω); upper bounds from greedy and DSATUR.

Bound	Value	Comes from
Lower	size of the largest clique ω(G)	all clique vertices need different colours
Upper	Δ + 1	greedy in any order
Upper	degeneracy + 1	greedy in smallest-last order
Exactly 2	G has an edge and no odd cycle	BFS

Java

1static boolean tryColour(int v, int k, int[] colour, List<Integer>[] adj, int used) {
2    if (v == colour.length) return true;
3    for (int c = 0; c < k && c <= used; c++) {                        // c <= used: never open a colour before the one below it
4        boolean ok = true;
5        for (int u : adj[v]) if (u < v && colour[u] == c) ok = false;
6        if (!ok) continue;
7        colour[v] = c;
8        if (tryColour(v + 1, k, colour, adj, Math.max(used, c + 1))) return true;
9    }
10    colour[v] = -1;
11    return false;
12}
13static int chromaticNumber(int n, List<Integer>[] adj) {              // smallest k that admits a proper k-colouring
14    for (int k = 1; k <= n; k++) {
15        int[] colour = new int[n];
16        if (tryColour(0, k, colour, adj, 0)) return k;
17    }
18    return n;
19}

Worst

O(n · k^n) in the worst case

Space

O(n)

Graph colouring: 2-colouring, greedy, DSATUR and the exact chromatic number

Interactive · edit the input

undirected graph · 6 vertices · 6 edges

Colour 0Colour 1Colour 2Colour 3Vertex being coloured

colour of each vertex

–0

–1

–2

–3

–4

–5

Setup

Step 1 / 8

Java

1@SuppressWarnings("unchecked")
2static List<Integer>[] adjacency(int n, int[][] edges) {
3    List<Integer>[] adj = new List[n];
4    for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
5    for (int[] e : edges) { adj[e[0]].add(e[1]); adj[e[1]].add(e[0]); }
6    return adj;
7}
8static int[] bipartiteColouring(int n, List<Integer>[] adj) {         // 2-colouring by BFS, or null when an odd cycle exists
9    int[] colour = new int[n];
10    Arrays.fill(colour, -1);
11    for (int s = 0; s < n; s++) {
12        if (colour[s] != -1) continue;
13        colour[s] = 0;
14        Deque<Integer> queue = new ArrayDeque<>(List.of(s));
15        while (!queue.isEmpty()) {
16            int u = queue.poll();
17            for (int v : adj[u]) {
18                if (colour[v] == colour[u]) return null;              // both ends of an edge got the same colour
19                if (colour[v] == -1) { colour[v] = 1 - colour[u]; queue.add(v); }
20            }
21        }
22    }
23    return colour;
24}
25static int[] greedyColouring(int n, List<Integer>[] adj) {            // vertices in index order, smallest free colour
26    int[] colour = new int[n];
27    Arrays.fill(colour, -1);
28    for (int v = 0; v < n; v++) {
29        boolean[] taken = new boolean[n + 1];
30        for (int u : adj[v]) if (colour[u] != -1) taken[colour[u]] = true;
31        int c = 0;
32        while (taken[c]) c++;
33        colour[v] = c;
34    }
35    return colour;
36}
37static int[] dsatur(int n, List<Integer>[] adj) {                     // always colour the most constrained vertex next
38    int[] colour = new int[n];
39    Arrays.fill(colour, -1);
40    for (int step = 0; step < n; step++) {
41        int pick = -1, bestSat = -1;
42        for (int v = 0; v < n; v++) {
43            if (colour[v] != -1) continue;
44            Set<Integer> seen = new HashSet<>();                      // saturation: distinct colours among neighbours
45            for (int u : adj[v]) if (colour[u] != -1) seen.add(colour[u]);
46            if (seen.size() > bestSat || (seen.size() == bestSat && adj[v].size() > adj[pick].size())) { pick = v; bestSat = seen.size(); }
47        }
48        boolean[] taken = new boolean[n + 1];
49        for (int u : adj[pick]) if (colour[u] != -1) taken[colour[u]] = true;
50        int c = 0;
51        while (taken[c]) c++;
52        colour[pick] = c;
53    }
54    return colour;
55}
56static boolean tryColour(int v, int k, int[] colour, List<Integer>[] adj, int used) {
57    if (v == colour.length) return true;
58    for (int c = 0; c < k && c <= used; c++) {                        // c <= used: never open a colour before the one below it
59        boolean ok = true;
60        for (int u : adj[v]) if (u < v && colour[u] == c) ok = false;
61        if (!ok) continue;
62        colour[v] = c;
63        if (tryColour(v + 1, k, colour, adj, Math.max(used, c + 1))) return true;
64    }
65    colour[v] = -1;
66    return false;
67}
68static int chromaticNumber(int n, List<Integer>[] adj) {              // smallest k that admits a proper k-colouring
69    for (int k = 1; k <= n; k++) {
70        int[] colour = new int[n];
71        if (tryColour(0, k, colour, adj, 0)) return k;
72    }
73    return n;
74}

Live state

0 vertices coloured

edges

No condition evaluated on this step

Execution trace (dry run table)Show 8 steps

Step	Line	State	What happens
1	L25	n=6 edges=6	Greedy colouring: take the vertices in index order and give each the smallest colour that none of its already coloured neighbours uses. It never needs more than (maximum degree + 1) colours, but the order decides how many it really uses.
2	L33	vertex=0 colour=0 colours_used=1	Vertex 0: neighbours already use no colour, so the smallest free colour is 0.
3	L33	vertex=1 colour=0 colours_used=1	Vertex 1: neighbours already use no colour, so the smallest free colour is 0.
4	L33	vertex=2 colour=1 colours_used=2	Vertex 2: neighbours already use {0}, so the smallest free colour is 1.
5	L33	vertex=3 colour=1 colours_used=2	Vertex 3: neighbours already use {0}, so the smallest free colour is 1.
6	L33	vertex=4 colour=2 colours_used=3	Vertex 4: neighbours already use {0,1}, so the smallest free colour is 2.
7	L33	vertex=5 colour=2 colours_used=3	Vertex 5: neighbours already use {0,1}, so the smallest free colour is 2.
8	L35	return=3 colouring=0:0 1:0 2:1 3:1 4:2 5:2 proper=yes	3 colours used (greedy): 0:0 1:0 2:1 3:1 4:2 5:2. The colouring is proper, but it is only an upper bound on the chromatic number.

41.03.4

DSATUR heuristic

**DSATUR** (degree of saturation) is a greedy colouring with a smarter order. The **saturation** of an uncoloured vertex is the number of different colours among its coloured neighbours. At each step DSATUR picks the uncoloured vertex with the highest saturation (ties go to the vertex with more neighbours) and gives it the smallest free colour. The most constrained vertex is coloured first, while it still has choices.

DSATUR is exact on bipartite graphs, cycles and wheels, and it usually beats plain greedy by a wide margin. In the animation, the second preset runs it on the crown graph: it needs only 2 colours, where index-order greedy needed 3 (the colouring is 0:0 1:1 2:0 3:1 4:0 5:1).

The simple implementation below is O(V^2 + V·E); a heap or bucket structure makes it faster. For exam timetabling and register allocation, DSATUR is the usual starting point, often followed by local search or an exact solver for the hardest part.

Java

1static int[] dsatur(int n, List<Integer>[] adj) {                     // always colour the most constrained vertex next
2    int[] colour = new int[n];
3    Arrays.fill(colour, -1);
4    for (int step = 0; step < n; step++) {
5        int pick = -1, bestSat = -1;
6        for (int v = 0; v < n; v++) {
7            if (colour[v] != -1) continue;
8            Set<Integer> seen = new HashSet<>();                      // saturation: distinct colours among neighbours
9            for (int u : adj[v]) if (colour[u] != -1) seen.add(colour[u]);
10            if (seen.size() > bestSat || (seen.size() == bestSat && adj[v].size() > adj[pick].size())) { pick = v; bestSat = seen.size(); }
11        }
12        boolean[] taken = new boolean[n + 1];
13        for (int u : adj[pick]) if (colour[u] != -1) taken[colour[u]] = true;
14        int c = 0;
15        while (taken[c]) c++;
16        colour[pick] = c;
17    }
18    return colour;
19}

Worst

O(V² + V · E) with this simple scan

Space

O(V)

Graph colouring: 2-colouring, greedy, DSATUR and the exact chromatic number

Interactive · edit the input

undirected graph · 6 vertices · 6 edges

Colour 0Colour 1Colour 2Colour 3Vertex being coloured

colour of each vertex

–0

–1

–2

–3

–4

–5

Setup

Step 1 / 8

Java

1@SuppressWarnings("unchecked")
2static List<Integer>[] adjacency(int n, int[][] edges) {
3    List<Integer>[] adj = new List[n];
4    for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
5    for (int[] e : edges) { adj[e[0]].add(e[1]); adj[e[1]].add(e[0]); }
6    return adj;
7}
8static int[] bipartiteColouring(int n, List<Integer>[] adj) {         // 2-colouring by BFS, or null when an odd cycle exists
9    int[] colour = new int[n];
10    Arrays.fill(colour, -1);
11    for (int s = 0; s < n; s++) {
12        if (colour[s] != -1) continue;
13        colour[s] = 0;
14        Deque<Integer> queue = new ArrayDeque<>(List.of(s));
15        while (!queue.isEmpty()) {
16            int u = queue.poll();
17            for (int v : adj[u]) {
18                if (colour[v] == colour[u]) return null;              // both ends of an edge got the same colour
19                if (colour[v] == -1) { colour[v] = 1 - colour[u]; queue.add(v); }
20            }
21        }
22    }
23    return colour;
24}
25static int[] greedyColouring(int n, List<Integer>[] adj) {            // vertices in index order, smallest free colour
26    int[] colour = new int[n];
27    Arrays.fill(colour, -1);
28    for (int v = 0; v < n; v++) {
29        boolean[] taken = new boolean[n + 1];
30        for (int u : adj[v]) if (colour[u] != -1) taken[colour[u]] = true;
31        int c = 0;
32        while (taken[c]) c++;
33        colour[v] = c;
34    }
35    return colour;
36}
37static int[] dsatur(int n, List<Integer>[] adj) {                     // always colour the most constrained vertex next
38    int[] colour = new int[n];
39    Arrays.fill(colour, -1);
40    for (int step = 0; step < n; step++) {
41        int pick = -1, bestSat = -1;
42        for (int v = 0; v < n; v++) {
43            if (colour[v] != -1) continue;
44            Set<Integer> seen = new HashSet<>();                      // saturation: distinct colours among neighbours
45            for (int u : adj[v]) if (colour[u] != -1) seen.add(colour[u]);
46            if (seen.size() > bestSat || (seen.size() == bestSat && adj[v].size() > adj[pick].size())) { pick = v; bestSat = seen.size(); }
47        }
48        boolean[] taken = new boolean[n + 1];
49        for (int u : adj[pick]) if (colour[u] != -1) taken[colour[u]] = true;
50        int c = 0;
51        while (taken[c]) c++;
52        colour[pick] = c;
53    }
54    return colour;
55}
56static boolean tryColour(int v, int k, int[] colour, List<Integer>[] adj, int used) {
57    if (v == colour.length) return true;
58    for (int c = 0; c < k && c <= used; c++) {                        // c <= used: never open a colour before the one below it
59        boolean ok = true;
60        for (int u : adj[v]) if (u < v && colour[u] == c) ok = false;
61        if (!ok) continue;
62        colour[v] = c;
63        if (tryColour(v + 1, k, colour, adj, Math.max(used, c + 1))) return true;
64    }
65    colour[v] = -1;
66    return false;
67}
68static int chromaticNumber(int n, List<Integer>[] adj) {              // smallest k that admits a proper k-colouring
69    for (int k = 1; k <= n; k++) {
70        int[] colour = new int[n];
71        if (tryColour(0, k, colour, adj, 0)) return k;
72    }
73    return n;
74}

Live state

0 vertices coloured

edges

No condition evaluated on this step

Execution trace (dry run table)Show 8 steps

Step	Line	State	What happens
1	L25	n=6 edges=6	Greedy colouring: take the vertices in index order and give each the smallest colour that none of its already coloured neighbours uses. It never needs more than (maximum degree + 1) colours, but the order decides how many it really uses.
2	L33	vertex=0 colour=0 colours_used=1	Vertex 0: neighbours already use no colour, so the smallest free colour is 0.
3	L33	vertex=1 colour=0 colours_used=1	Vertex 1: neighbours already use no colour, so the smallest free colour is 0.
4	L33	vertex=2 colour=1 colours_used=2	Vertex 2: neighbours already use {0}, so the smallest free colour is 1.
5	L33	vertex=3 colour=1 colours_used=2	Vertex 3: neighbours already use {0}, so the smallest free colour is 1.
6	L33	vertex=4 colour=2 colours_used=3	Vertex 4: neighbours already use {0,1}, so the smallest free colour is 2.
7	L33	vertex=5 colour=2 colours_used=3	Vertex 5: neighbours already use {0,1}, so the smallest free colour is 2.
8	L35	return=3 colouring=0:0 1:0 2:1 3:1 4:2 5:2 proper=yes	3 colours used (greedy): 0:0 1:0 2:1 3:1 4:2 5:2. The colouring is proper, but it is only an upper bound on the chromatic number.

41.03.5

Coloring complexity

Deciding whether a graph can be coloured with k colours is **NP-complete for every fixed k ≥ 3**, while k = 2 is the easy bipartite test and k = 1 is “no edges”. The optimisation problem is also hard to approximate: unless P = NP, no polynomial algorithm approximates χ(G) within n^(1 − ε).

There are bright spots. Interval graphs (and chordal graphs) are coloured optimally by a greedy rule in a perfect elimination order. Planar graphs can always be 4-coloured (the Four Colour Theorem, proved with computer assistance in 1976 and 1997) and 5-colouring a planar graph is easy and constructive. Trees need 2 colours; bounded-treewidth graphs are solved by dynamic programming.

In practice a mix is used: bounds from cliques and greedy, DSATUR for a good colouring, then exact search (SAT or DSATUR-based branch and bound) when the instance is small enough. The next lesson on planar graphs continues with the Four Colour Theorem's setting.

Graph class	Colouring
Bipartite	2 colours, BFS
Trees and forests	2 colours
Interval / chordal	optimal greedy in the right order
Planar	≤ 4 always, ≤ 5 constructively, ≤ 6 by greedy
General	NP-hard to decide for k ≥ 3, hard to approximate

Practice ladder

Now try it yourself

Easy

Is Graph Bipartite?

Medium

Possible Bipartition
Flower Planting With No Adjacent

Advanced

Maximum Students Taking Exam

Key takeaways

2-colourable = bipartite = no odd cycle, tested by BFS in O(V + E).
Greedy needs at most max degree + 1 colours but depends on the vertex order; DSATUR picks the most constrained vertex first.
The exact chromatic number is NP-hard; backtracking with symmetry breaking handles small graphs.