Introduction to Graph Coloring Medium 0 attempts
GeeksforGeeks ↗

Introduction to Graph Coloring

Medium GraphBFSDFS GeeksforGeeks

Given an undirected graph represented as an adjacency matrix and m colors, determine if the graph can be colored using at most m colors such that no two adjacent vertices share the same color. This is the classic graph m-coloring decision problem solved using backtracking.

Example 1:

Input: graph = [[0,1,1,1],[1,0,1,0],[1,1,0,1],[1,0,1,0]], m = 3
Output: true

Example 2:

Input: graph = [[0,1,1],[1,0,1],[1,1,0]], m = 2
Output: false
Sample Input
—
Sample Output
—
Constraints
  • 1 <= V <= 50
  • 0 <= E <= V*(V-1)/2
  • 1 <= M (colors) <= V
Test Cases
Case 1
Args: [[[0,1,1,1],[1,0,1,0],[1,1,0,1],[1,0,1,0]],3] Expected: true
Case 2
Args: [[[0,1,1],[1,0,1],[1,1,0]],2] Expected: false
Topics
GraphBFSDFS

Approach: Backtracking

Try assigning colors 1 to m to each vertex in sequence. Before assigning, check if any adjacent vertex already has the same color. If no valid color exists for a vertex, backtrack.

function introductionToGraphColoring(graph, m) {
  const n = graph.length;
  const colors = new Array(n).fill(0);
  function isSafe(v, c) {
    for (let i = 0; i < n; i++)
      if (graph[v][i] && colors[i] === c) return false;
    return true;
  }
  function solve(v) {
    if (v === n) return true;
    for (let c = 1; c <= m; c++) {
      if (isSafe(v, c)) {
        colors[v] = c;
        if (solve(v + 1)) return true;
        colors[v] = 0;
      }
    }
    return false;
  }
  return solve(0);
}

Time Complexity: O(m^V)

Space Complexity: O(V)

Saved in this browser only. Private to you.

JavaScript