Graph Colouring by Backtracking

1Produce a colouring, do not classify the decision

A proper colouring of an undirected graph gives every vertex a colour so that the two ends of every edge have different colours. The search problem, given G and an integer m, is to write down such an assignment with colours \{1,\ldots,m\}, or to say that none exists.

That is a different outcome from chromatic-number decision, which only asks whether \chi(G) \le k and, for k \ge 3, is NP-complete. This topic builds the assignment. The NPC sentence is already taught; it is the reason the search is allowed to be exponential, not a second proof.

Same triangle ABC that forced three colours in the NPC topic. This page's job is to search, not to restate that 3-colouring is NPC.

Two questions, one graph

1. DecisionDoes a k-colouring exist? Certificate = the colour list. NPC for k \ge 3.
2. SearchWrite the colour list, or report failure. This topic.
3. Do not mixA successful search on one triangle is not a polynomial algorithm for every graph.

2Try a colour, check neighbours, unchoose

Fix an order of the vertices, v_0,\ldots,v_{n-1}. At v_i try each colour c \in \{1,\ldots,m\}. A colour is legal when no already-coloured neighbour of v_i holds c. If it is legal, assign it, recurse to v_{i+1}, then unassign it and try the next c. Success at i=n is a complete colouring.

That is the same choose-explore-unchoose skeleton as N-Queens. The clash test is the only new piece: a neighbour's colour, not a shared column or diagonal.

One vertex

1. Try cEach colour in 1..m.
2. Clash?Reject c if some neighbour already holds c.
3. UnchooseOn failure of the recursive call, clear v_i and try the next c.

m-colouring

def colour(graph, m):
    n = len(graph)
    col = [0] * n

    def ok(v, c):
        return all(col[u] != c for u in graph[v])

    def rec(v):
        if v == n:
            return True
        for c in range(1, m + 1):
            if ok(v, c):
                col[v] = c
                if rec(v + 1):
                    return True
                col[v] = 0
        return False

    return col if rec(0) else None

3Triangle plus a pendant-free D, m = 3

Running graph: vertices A, B, C, D. Edges AB, BC, CD, DA, AC. A, B, C are a triangle, so m=2 is impossible. D is adjacent to A and C only.

Order A, B, C, D. A=1, B=2 (1 clashes with A), C=3 (1 and 2 taken by neighbours A and B), D=2 (1 and 3 taken by A and C; 2 is free because DB is not an edge). First success: (1,2,3,2).

Figure. Triangle ABC uses three colours. D reuses B's colour 2 because the edge DB is absent. Roles mark c1 / c2 / c3, not good versus bad.

First successful branch

1. A, BA=1. B rejects 1, takes 2.
2. CNeighbours A,B hold 1,2 — C takes 3.
3. DNeighbours A,C hold 1,3 — D takes 2.

Coding lab. 3-colour the square plus diagonal runs in the app, with checks on your output.

4Prune on a clash; do not backtrack 2-colouring

A colour that already sits on a neighbour is rejected before the recursive call. That prune is the whole speedup: the subtree in which v_i holds a clashing c is empty of solutions, so it is not explored. On the running graph, B never tries colour 1; C never tries 1 or 2.

When m=2, do not run this tree. A graph is 2-colourable if and only if it is bipartite, and BFS (or DFS) 2-colours each component or reports an odd cycle in linear time. The running graph has a triangle, so BFS reports failure without a 2^4 search. Backtracking is the tool for a general m, usually m \ge 3.

Same A-B-C-D figure. For m=2 the triangle is an odd cycle; BFS reports that without growing a 16-leaf tree.

Pick the algorithm

1. m=2BFS 2-colour. Odd cycle → no.
2. m \ge 3, small nBacktracking as in the listing.
3. Large n, m \ge 3Exact search may be hopeless; that is the NPC sentence, not a new proof.