Graph Colouring Problem

The problem, simply

You get a graph: countries (dots) and borders (lines). Give every country a colour so that two countries sharing a border never have the same colour. Use as few colours as possible.

The smallest possible number is called the chromatic number. Finding it exactly is famously hard: nobody knows a fast method for big graphs. So interviews ask two things: how to find the exact answer on a small graph (Way 1), and the fast greedy method that real programs use (Way 2), together with what it can and cannot promise.

A story to remember it

Picture it

Examples

Way 1: the simple way

Find the true minimum by trying. Ask "can it be done with 1 colour?", then 2, then 3, and so on. For each number k, try colours country by country with backtracking: give the next country a colour no neighbour has, move on, and undo when you get stuck.

1. For k = 1, 2, 3, ...
2. Try to colour countries 0 to V - 1 with colours 0 to k - 1, skipping any colour a neighbour already has.
3. If a country has no colour left, go back and change the previous country.
4. The first k that works is the answer.

import java.util.*;

class Solution {
    public int minColours(int V, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }
        int[] colour = new int[V];
        for (int k = 1; k <= V; k++) {
            Arrays.fill(colour, -1);
            if (place(adj, 0, k, colour)) return k;    // first k that works is the smallest
        }
        return V;
    }

    private boolean place(List<List<Integer>> adj, int u, int k, int[] colour) {
        if (u == colour.length) return true;           // everyone is coloured
        for (int c = 0; c < k; c++) {
            boolean free = true;
            for (int v : adj.get(u)) if (colour[v] == c) { free = false; break; }
            if (!free) continue;
            colour[u] = c;
            if (place(adj, u + 1, k, colour)) return true;
            colour[u] = -1;                            // undo and try the next colour
        }
        return false;
    }
}

How long it takes: for each k there can be up to k^V ways to colour, and each check looks at borders, so roughly O(k^V * (V + E)) where k is the answer. Fine for 10 or 15 countries, hopeless for 100. Extra room: the colours and the recursion, O(V).

Way 2: the clever way

Give up on the perfect answer and be quick. Go through the countries in order. For each one, mark the colours its already coloured neighbours use, and take the smallest colour that is not marked.

1. Every country starts with no colour.
2. For country u: mark the colours of its coloured neighbours.
3. Give u the smallest unmarked colour. Then clear the marks.

This always gives a correct colouring. It never uses more than (most neighbours any country has) + 1 colours, because a country with d neighbours can see at most d colours, so one of the first d + 1 must be free.

import java.util.*;

class Solution {
    // colour[u] is 0 for the first colour, 1 for the second, and so on
    public int[] greedyColour(int V, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }
        int[] colour = new int[V];
        Arrays.fill(colour, -1);
        boolean[] taken = new boolean[V + 1];
        for (int u = 0; u < V; u++) {
            for (int v : adj.get(u)) if (colour[v] != -1) taken[colour[v]] = true;
            int c = 0;
            while (taken[c]) c++;                     // first free crayon
            colour[u] = c;
            for (int v : adj.get(u)) if (colour[v] != -1) taken[colour[v]] = false;   // clean the marks
        }
        return colour;
    }
}

How long it takes: each country looks at its own borders twice, so O(V + E) in total. Extra room: the colours and the marks, O(V).

Watch out for

• Clearing the marks. If you use one shared taken array, unmark after each country, or use a fresh array each time.
• Only coloured neighbours matter. A neighbour without a colour yet does not block anything.
• A self loop (a country bordering itself) makes colouring impossible. Check the input if it can contain one.
• Checking with two colours is easy. Breadth first search can decide two-colourable (bipartite) in O(V + E); three or more colours is the hard case.

What interviewers ask next

• How can you help greedy pick fewer colours? Colour the countries with the most neighbours first (the Welsh Powell order), or always pick the country whose neighbours already use the most different colours (DSatur).
• Is there always an order where greedy is perfect? Yes. Colour all countries of the best colouring's first colour first, then the second, and so on. Finding that order is as hard as the problem.
• Where is this used? Exam timetables (exams that share a student need different time slots), radio frequencies for nearby towers, and register allocation in compilers.
• Can every map on paper be coloured with 4 colours? Yes, that is the four colour theorem. It holds for maps drawn flat without crossing borders, not for every graph.
• Given a number m, can the graph be coloured with m colours? That is the M colouring problem: backtracking like Way 1 with a fixed k = m.

Remember this

Grown-up words: countries are vertices, borders are edges, crayons are colours, the smallest number of crayons is the chromatic number, colouring with two colours is checking bipartiteness, and picking the first free colour is greedy (first fit) colouring.