Graph / m-colouring problem

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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);
}