M-Coloring Problem | Practice Medium 0 attempts
GeeksforGeeks ↗

M-Coloring Problem | Practice

Medium BacktrackingRecursion GeeksforGeeks

You're given an undirected graph as an adjacency list, along with an integer m. Decide whether the graph's vertices can be colored using no more than m colors so that every pair of adjacent vertices ends up with different colors.

Edge cases: Graph with no edges (always colorable with m ≥ 1). m = 1 only works if there are no edges. Disconnected components.

Input Format
Implement canColor(graph, m, n). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
m = 3
n = 4
Output
true

Example 2

Input
graph = [[1,2],[0,2],[0,1]]
m = 2
n = 3
Output
false
Constraints
  • 1 <= n <= 20
  • 1 <= m <= n
  • graph is an adjacency list for a simple undirected graph with vertices 0 through n-1.
Test Cases (2)
Case 1
Args: [[[1,2,3],[0,2],[0,1,3],[0,2]],3,4] Expected: true
Case 2
Args: [[[1,2],[0,2],[0,1]],2,3] Expected: false
Topics
BacktrackingRecursion

Approach: Backtracking

Assign colors to vertices one by one. For each vertex, try all m colors and check if any neighbor already has that color. If the assignment is safe, recurse to the next vertex. If no color works, backtrack.

javascript
function canColor(graph, m, n) {
  const colors = new Array(n).fill(0);

  function isSafe(node, color) {
    for (const neighbor of (graph[node] || [])) {
      if (colors[neighbor] === color) return false;
    }
    return true;
  }

  function solve(node) {
    if (node === n) return true;

    for (let c = 1; c <= m; c++) {
      if (isSafe(node, c)) {
        colors[node] = c;
        if (solve(node + 1)) return true;
        colors[node] = 0;
      }
    }
    return false;
  }

  return solve(0);
}

Time Complexity: O(m^n) worst case

Space Complexity: O(n) for the color array and recursion stack

Saved in this browser only. Private to you.

JavaScript