M-Coloring Problem | Practice | Problems

Given an undirected graph represented as an adjacency list and an integer m, determine whether the graph can be colored using at most m colors such that no two adjacent vertices share the same color.

Example 1:

Input: graph = {0:[1,2], 1:[0,2], 2:[0,1]}, m = 3
Output: true
Explanation: Triangle graph needs 3 colors — assign 0→Red, 1→Green, 2→Blue.

Example 2:

Input: graph = {0:[1,2], 1:[0,2], 2:[0,1]}, m = 2
Output: false
Explanation: A triangle cannot be 2-colored.

Example 3:

Input: graph = {0:[1,3], 1:[0,2], 2:[1,3], 3:[2,0]}, m = 2
Output: true
Explanation: A 4-cycle is bipartite and 2-colorable.

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

Sample Input

N = 4, M = 3, E = 5

Sample Output

1 (True)

Constraints

1 <= V <= 20
1 <= E <= V*(V-1)/2
1 <= M <= V

Test Cases

Case 1

Args: [[[0,1,1,1],[1,0,1,0],[1,1,0,1],[1,0,1,0]],3,4] Expected: true

Case 2

Args: [[[0,1,1],[1,0,1],[1,1,0]],2,3] Expected: false

Topics

Backtracking Recursion

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.

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.