BackTrackingProblem 6 of 19

m Coloring Problem

Brute Force
Time: O(m^n)
Space: O(n)
Optimal
Time: O(m^n)
Space: O(n)

Problem Statement

Given an undirected graph and a number m, determine if the graph can be colored with at most m colors such that no two adjacent vertices have the same color. Return true if possible, else return false.

Example:

Input: graph = [[1,2,3], [0,2], [0,1,3], [0,2]] // adjacency list m = 3 0 --- 1 | \ | | \ | 3 --- 2 Output: true Explanation: We can color: 0->Red, 1->Green, 2->Red, 3->Green Or: 0->Color1, 1->Color2, 2->Color3, 3->Color2

Approach 1: Brute Force (Try All Combinations)

Intuition

Try assigning each color (1 to m) to each vertex. Before assigning, check if any adjacent vertex has the same color. Use backtracking when an assignment fails.

Algorithm

  1. Start with vertex 0
  2. Try all m colors for current vertex
  3. Check if color is safe (no adjacent vertex has same color)
  4. If safe, assign and recurse for next vertex
  5. If all vertices colored, return true
  6. Backtrack if stuck
java
import java.util.*;

class Solution {
    public boolean isSafe(int node, List<List<Integer>> graph, int[] color, int c) {
        for (int neighbor : graph.get(node)) {
            if (color[neighbor] == c) {
                return false;
            }
        }
        return true;
    }
    
    public boolean solve(int node, List<List<Integer>> graph, int[] color, int m, int n) {
        // All vertices colored
        if (node == n) {
            return true;
        }
        
        // Try all m colors
        for (int c = 1; c <= m; c++) {
            if (isSafe(node, graph, color, c)) {
                color[node] = c;
                
                if (solve(node + 1, graph, color, m, n)) {
                    return true;
                }
                
                color[node] = 0;  // Backtrack
            }
        }
        
        return false;
    }
    
    public boolean graphColoring(List<List<Integer>> graph, int m, int n) {
        int[] color = new int[n];
        return solve(0, graph, color, m, n);
    }
}

Complexity Analysis

  • Time Complexity: O(m^n) - m choices for each of n vertices
  • Space Complexity: O(n) - For color array and recursion stack

Approach 2: Optimal (With Adjacency Matrix)

Intuition

Same backtracking approach but with adjacency matrix for O(1) edge lookup. Also includes optimizations like checking if minimum colors needed exceeds m.

Algorithm

  1. Use adjacency matrix for faster neighbor lookup
  2. Apply same backtracking with color array
  3. Early termination if impossible
java
import java.util.*;

class Solution {
    public boolean isSafe(int node, boolean[][] adj, int[] color, int c, int n) {
        for (int i = 0; i < n; i++) {
            if (adj[node][i] && color[i] == c) {
                return false;
            }
        }
        return true;
    }
    
    public boolean solve(int node, boolean[][] adj, int[] color, int m, int n) {
        if (node == n) {
            return true;
        }
        
        for (int c = 1; c <= m; c++) {
            if (isSafe(node, adj, color, c, n)) {
                color[node] = c;
                
                if (solve(node + 1, adj, color, m, n)) {
                    return true;
                }
                
                color[node] = 0;
            }
        }
        
        return false;
    }
    
    public boolean graphColoring(int n, int[][] edges, int m) {
        // Build adjacency matrix
        boolean[][] adj = new boolean[n][n];
        for (int[] edge : edges) {
            adj[edge[0]][edge[1]] = true;
            adj[edge[1]][edge[0]] = true;
        }
        
        int[] color = new int[n];
        return solve(0, adj, color, m, n);
    }
}

Complexity Analysis

  • Time Complexity: O(m^n) - Same worst case
  • Space Complexity: O(n²) - For adjacency matrix

Approach 3: Print All Colorings

Intuition

Instead of returning at first valid coloring, continue exploration to find all valid colorings.

java
import java.util.*;

class Solution {
    public void printColoring(int[] color) {
        System.out.print("Coloring: ");
        for (int c : color) {
            System.out.print(c + " ");
        }
        System.out.println();
    }
    
    public boolean isSafe(int node, List<List<Integer>> graph, int[] color, int c) {
        for (int neighbor : graph.get(node)) {
            if (color[neighbor] == c) {
                return false;
            }
        }
        return true;
    }
    
    public void solve(int node, List<List<Integer>> graph, int[] color,
                      int m, int n, List<int[]> colorings) {
        if (node == n) {
            colorings.add(color.clone());
            return;
        }
        
        for (int c = 1; c <= m; c++) {
            if (isSafe(node, graph, color, c)) {
                color[node] = c;
                solve(node + 1, graph, color, m, n, colorings);
                color[node] = 0;
            }
        }
    }
    
    public List<int[]> getAllColorings(List<List<Integer>> graph, int m, int n) {
        int[] color = new int[n];
        List<int[]> colorings = new ArrayList<>();
        solve(0, graph, color, m, n, colorings);
        return colorings;
    }
}

Complexity Analysis

  • Time Complexity: O(m^n × n) - All colorings enumerated
  • Space Complexity: O(n × number of colorings)

Key Takeaways

  1. Chromatic Number: Minimum colors needed to color a graph
  2. Bipartite Check: A graph is bipartite iff it's 2-colorable
  3. Greedy Approach: For approximation, use greedy coloring (not optimal)
  4. Four Color Theorem: Any planar graph can be colored with at most 4 colors
  5. NP-Complete: Determining chromatic number is NP-complete for general graphs
  6. Applications: Scheduling, register allocation, map coloring
Previous
Sudoku Solver
Next
Print all palindromic partitions of a string