Graph coloring by backtracking: Examples & Code

Algorithm Visualizations November 16, 2026 javascript

Published by Dimitris Kougioumtzis · Updated

Assign colors in vertex order, reject conflicts with neighbors, and undo failed choices. This solves k-color feasibility, not minimum coloring in one run.

Visit vertices in index order and try colors in ascending order. Reject a color if an adjacent vertex already uses it, and undo assignments when no continuation works.

Open the 3D visualization

Graph coloring by backtracking example state preview
Preview of the example's final state. Complete values are available in the worked example and interactive timeline.

When to use Graph coloring by backtracking

Teaching bounded constraint satisfaction and deciding whether a graph admits a proper coloring with a specified number of colors.

Choosing an alternative

This backtracking solver decides k-color feasibility. It does not compute the chromatic number in one run and is not a greedy coloring heuristic.

Worked example: input and state changes

Example input

0,1,1,1;1,0,1,1;1,1,0,1;1,1,1,0 | 4

These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.

  1. Step 0: 0 means unassigned. Try colors 1 through 4 in vertex order.

    State at this checkpoint
    {
      "values": [
        0,
        0,
        0,
        0
      ],
      "active": [],
      "kind": "graph",
      "directed": false,
      "chosen": [],
      "visited": [],
      "vertexColors": [
        0,
        0,
        0,
        0
      ],
      "nodeLabels": [
        "0 unassigned",
        "1 unassigned",
        "2 unassigned",
        "3 unassigned"
      ],
      "result": 0,
      "output": [
        0,
        0,
        0,
        0
      ]
    }
  2. Step 3: Assign color 2 to vertex 1.

    State at this checkpoint
    {
      "values": [
        1,
        2,
        0,
        0
      ],
      "active": [
        1
      ],
      "kind": "graph",
      "directed": false,
      "chosen": [],
      "visited": [],
      "vertexColors": [
        1,
        2,
        0,
        0
      ],
      "nodeLabels": [
        "0 color 1",
        "1 color 2",
        "2 unassigned",
        "3 unassigned"
      ],
      "result": 0,
      "output": [
        1,
        2,
        0,
        0
      ]
    }
  3. Step 6: Assign color 3 to vertex 2.

    State at this checkpoint
    {
      "values": [
        1,
        2,
        3,
        0
      ],
      "active": [
        2
      ],
      "kind": "graph",
      "directed": false,
      "chosen": [],
      "visited": [],
      "vertexColors": [
        1,
        2,
        3,
        0
      ],
      "nodeLabels": [
        "0 color 1",
        "1 color 2",
        "2 color 3",
        "3 unassigned"
      ],
      "result": 0,
      "output": [
        1,
        2,
        3,
        0
      ]
    }
  4. Step 8: Color 2 conflicts at vertex 3.

    State at this checkpoint
    {
      "values": [
        1,
        2,
        3,
        0
      ],
      "active": [
        3
      ],
      "kind": "graph",
      "directed": false,
      "chosen": [],
      "visited": [],
      "vertexColors": [
        1,
        2,
        3,
        0
      ],
      "nodeLabels": [
        "0 color 1",
        "1 color 2",
        "2 color 3",
        "3 unassigned"
      ],
      "result": 0,
      "output": [
        1,
        2,
        3,
        0
      ]
    }
  5. Step 11: Found a proper 4-coloring.

    State at this checkpoint
    {
      "values": [
        1,
        2,
        3,
        4
      ],
      "active": [],
      "kind": "graph",
      "directed": false,
      "chosen": [],
      "visited": [],
      "vertexColors": [
        1,
        2,
        3,
        4
      ],
      "nodeLabels": [
        "0 color 1",
        "1 color 2",
        "2 color 3",
        "3 color 4"
      ],
      "result": 1,
      "output": [
        1,
        2,
        3,
        4
      ]
    }

Expected final state

Found a proper 4-coloring.

Complexity and input bounds

Family: Backtracking. Time complexity: O(n * k^n) bounded search.

Implementation detail: At most seven vertices and four available colors bound the search. Both WebGL and 2D show distinct colors and textual color IDs; zero means unassigned. Downloads use a symmetric adjacency matrix and return the first assignment in vertex/color lexicographic order, or failure with all output entries zero.

Space complexity: O(n) traversal state and color output, excluding the adjacency matrix and recorded frames.

Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.

Symmetric 0/1 adjacency matrix, 1..7 vertices; rows separated by ; | 1..4 colors. Self loops make coloring impossible.

The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.

Common mistakes and limitations

A self loop makes every proper coloring impossible. An empty graph can use zero colors; a nonempty graph cannot. Restore a failed vertex assignment before exploring a different branch.

Further reading

For background on algorithm analysis and the JavaScript function interface:

Editorial and testing approach · Browse all algorithm guides

Complete JavaScript implementation

javascript
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
// Symmetric row-major 0/1 adjacency matrix, n 0..7 vertices, k 0..4 available colors. Self loops are impossible. Returns 1 and writes the first proper assignment in vertex/color lexicographic search order; otherwise returns 0 with all n output entries zero. Colors numbered 1..k, 0 unassigned. Output capacity at least n. Empty graph is colorable even with k=0; a nonempty graph with k=0 is not. O(n*k^n) bounded time, O(n) traversal scratch excluding adjacency/output. This tests k-color feasibility, not minimum coloring. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation.
function algorithm(adjacency, n, k, output) {
    for (let i = 0; i < n; i++) { output[i] = 0; }
    for (let i = 0; i < n; i++) { if (adjacency[i*n+i] != 0) { return 0; } }
    let vertex = 0; let candidate = 0; let legal = 0;
    while (vertex >= 0) { if (vertex == n) { return 1; } candidate = output[vertex]+1; output[vertex] = 0;
     while (candidate <= k) { legal = 1; for (let other = 0; other < n; other++) { if (adjacency[vertex*n+other] != 0 && output[other] == candidate) { legal = 0; break; } } if (legal != 0) { break; } candidate++; }
     if (candidate > k) { vertex--; } else { output[vertex] = candidate; vertex++; if (vertex < n) { output[vertex] = 0; } }
    }
    return 0;
}

Source

Related primary research on backtrack programs, not an asserted original graph-coloring paper. The playground uses fixed vertex order and explicit exhaustive k-color feasibility.