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.
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.
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 ] }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 ] }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 ] }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 ] }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:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
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.
- Estimating the efficiency of backtrack programs
Donald E. Knuth (1975). Related research paper.