Problem

Given an undirected graph and a number m (m colors), determine if the graph can be colored with at most m colors such that no two adjacent vertices are colored with the same color. Coloring means assigning a color to each vertex.

OR

Given an undirected graph represented as an adjacency matrix and an integer k, write a function to determine whether each vertex in the graph can be colored such that no two adjacent vertices share the same color using at most k colors.

Input Format

  • n: Number of vertices (integer)
  • edges: List of edges, where each edge is represented as a pair [u, v] indicating an undirected edge between vertex u and vertex v (0-based indexing)
  • m: Maximum number of colors (integer)

Examples

Example 1

graph TB;

subgraph I["Input"]
	0(0)--- 1(1) & 2(2) & 3(3)
	1 --- 2
	2 --- 3
end

subgraph O["Output"];
	A(0) --- B(1) & C(2) & D(3)
	B --- C
	C --- D
end

I ~~~ O

style A fill:#FF9933
style B fill:#3399FF
style D fill:#3399FF
style C fill:#99FF33
  
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

Input:
n = 4
edges = [[0, 1], [0, 2], [0, 3], [1, 2], [2, 3]]
m = 3

Output:
true
We can build adjacency matrix like:
graph = [ 
	[ 0, 1, 1, 1 ],
	[ 1, 0, 1, 0 ],
	[ 1, 1, 0, 1 ],
	[ 1, 0, 1, 0 ],
]
And one possible coloring can be [1, 2, 3, 2]
Similar Problems

Solution

Solution

Method 1 – Brute Force (Naive)

Intuition

Try all possible ways to assign m colors to n vertices, and check if any assignment is valid (no two adjacent vertices share the same color).

Approach

  1. Generate all possible assignments of m colors to n vertices (there are m^n possible assignments).
  2. For each assignment, check all edges in the edges list:
    • For each edge [u, v], check if the colors assigned to u and v are different.
  3. If a valid coloring is found, return true; otherwise, return false.

Complexity

  • ⏰ Time complexity: O(m^n * n^2) (or O(m^n * E)), where n is the number of vertices and E is the number of edges. For each of the m^n assignments, we check all edges.
  • 🧺 Space complexity: O(n), for storing a coloring assignment.

Method 2 – Backtracking

Intuition

Assign colors to vertices one by one, backtracking if a conflict is found, to efficiently search for a valid coloring.

Approach

  1. Start from the first vertex.
  2. For each color from 1 to m:
    • Check if assigning this color to the current vertex is safe (no adjacent vertex has the same color).
    • If safe, assign the color and move to the next vertex recursively.
    • If not, try the next color.
  3. If all vertices are assigned, return the coloring; otherwise, backtrack.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

#include <vector>
using namespace std;

class Solution {
public:
    // Build adjacency matrix from edge list
    vector<vector<int>> buildGraph(int n, const vector<pair<int,int>>& edges) {
        vector<vector<int>> graph(n, vector<int>(n, 0));
        for (auto& e : edges) {
            graph[e.first][e.second] = 1;
            graph[e.second][e.first] = 1;
        }
        return graph;
    }
    bool isSafe(int v, const vector<vector<int>>& graph, const vector<int>& color, int c) {
        for (int i = 0; i < graph.size(); ++i)
            if (graph[v][i] && color[i] == c) return false;
        return true;
    }
    bool solve(int v, const vector<vector<int>>& graph, int m, vector<int>& color) {
        if (v == graph.size()) return true;
        for (int c = 1; c <= m; ++c) {
            if (isSafe(v, graph, color, c)) {
                color[v] = c;
                if (solve(v+1, graph, m, color)) return true;
                color[v] = 0;
            }
        }
        return false;
    }
    bool graphColoring(int n, const vector<pair<int,int>>& edges, int m, vector<int>& coloring) {
        vector<vector<int>> graph = buildGraph(n, edges);
        coloring.assign(n, 0);
        return solve(0, graph, m, coloring);
    }
};
// Usage:
// int n = 4;
// vector<pair<int,int>> edges = {{0,1},{0,2},{0,3},{1,2},{2,3}};
// int m = 3;
// vector<int> coloring;
// bool res = Solution().graphColoring(n, edges, m, coloring);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

import java.util.*;
public class Solution {
    public boolean graphColoring(int n, int[][] edges, int m, int[] coloring) {
        int[][] graph = new int[n][n];
        for (int[] e : edges) {
            graph[e[0]][e[1]] = 1;
            graph[e[1]][e[0]] = 1;
        }
        Arrays.fill(coloring, 0);
        return solve(0, graph, m, coloring);
    }
    private boolean solve(int v, int[][] graph, int m, int[] color) {
        if (v == graph.length) return true;
        for (int c = 1; c <= m; ++c) {
            if (isSafe(v, graph, color, c)) {
                color[v] = c;
                if (solve(v+1, graph, m, color)) return true;
                color[v] = 0;
            }
        }
        return false;
    }
    private boolean isSafe(int v, int[][] graph, int[] color, int c) {
        for (int i = 0; i < graph.length; ++i)
            if (graph[v][i] == 1 && color[i] == c) return false;
        return true;
    }
    // Usage:
    // int n = 4;
    // int[][] edges = {{0,1},{0,2},{0,3},{1,2},{2,3}};
    // int m = 3;
    // int[] coloring = new int[n];
    // boolean res = new Solution().graphColoring(n, edges, m, coloring);
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class Solution:
    def build_graph(self, n, edges):
        graph = [[0]*n for _ in range(n)]
        for u, v in edges:
            graph[u][v] = 1
            graph[v][u] = 1
        return graph

    def is_safe(self, v, graph, color, c):
        n = len(graph)
        for i in range(n):
            if graph[v][i] and color[i] == c:
                return False
        return True

    def solve(self, v, graph, m, color):
        n = len(graph)
        if v == n:
            return True
        for c in range(1, m+1):
            if self.is_safe(v, graph, color, c):
                color[v] = c
                if self.solve(v+1, graph, m, color):
                    return True
                color[v] = 0
        return False

    def graphColoring(self, n, edges, m):
        graph = self.build_graph(n, edges)
        color = [0] * n
        if self.solve(0, graph, m, color):
            return True, color
        return False, []

# Usage:
# n = 4
# edges = [[0,1],[0,2],[0,3],[1,2],[2,3]]
# m = 3
# res, coloring = Solution().graphColoring(n, edges, m)

Complexity

  • ⏰ Time complexity: O(n^m), where n is the number of vertices in the graph and m is the maximum number of colors allowed (which can be as high as the number of vertices in the worst case).
    • In the worst case, the algorithm might try coloring each vertex with all possible colors and backtrack if a conflict arises. This can lead to an exponential number of possibilities, resulting in a time complexity of O(n^m),
  • 🧺 Space complexity: O(n)