Graph / m-colouring problem
Problem
Return true if the graph's vertices can be coloured with at most m colours so that no edge joins two vertices of the same colour.
Example 1
Input: 4 vertices, edges 0–1, 1–2, 2–3, 3–0, 0–2, m = 3 Output: true
Also asked as: Graph ColouringProblem · M-ColouringProblem · m Coloring Problem
Test cases
Case 1
Input: 4, [[1,3,2],[0,2],[1,3,0],[2,0]], 3 Expected: true
Case 2
Input: 4, [[1,3,2],[0,2],[1,3,0],[2,0]], 2 Expected: false
Case 3
Input: 2, [[1],[0]], 1 Expected: false
Case 4
Input: 3, [[],[],[]], 1 Expected: true
View solutionHide solution1 approach
1. Backtracking over vertices
Time O(mⱽ)Space O(V)
Try each colour 1..m for the current vertex if no neighbour already has it; recurse; backtrack.
function canColor(n, adj, m) { const color = new Array(n).fill(0); const ok = (u, c) => adj[u].every((v) => color[v] !== c); const bt = (u) => { if (u === n) return true; for (let c = 1; c <= m; c++) { if (ok(u, c)) { color[u] = c; if (bt(u + 1)) return true; color[u] = 0; } } return false; }; return bt(0);}