Introduction to Graph Coloring Medium 0 attempts
GeeksforGeeks ↗

Introduction to Graph Coloring

Medium GraphBFSDFS GeeksforGeeks

You're given an undirected graph as an adjacency matrix, along with a budget of m colors. Decide whether every vertex can be assigned one of those m colors so that no two vertices joined by an edge end up with the same color. This is the well-known graph m-coloring decision problem, typically tackled with a backtracking search over color assignments.

Input Format
Implement introductionToGraphColoring(graph, m). 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 = [[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
Constraints
  • 1 <= V <= 50
  • 1 <= m <= V
  • graph is a symmetric V × V 0/1 adjacency matrix with zero diagonal.
Test Cases (2)
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.

javascript
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