Log inSign up
mediumGeeksforGeeksNot Started

M-Coloring Problem

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Backtracking
Solve on GeeksforGeeks
Lesson

Problem Statement

Given an undirected graph and an integer m, determine if the graph can be colored with at most m colors such that no two adjacent vertices of the graph are colored with the same color. Here coloring of a graph means the assignment of colors to all vertices.

Return true if the graph can be colored with m colors, otherwise return false.

Example 1:

Input: V = 4, m = 3, E = 5, edges = [[0,1],[1,2],[2,3],[3,0],[0,2]]
Output: true
Explanation: Vertices can be colored as: vertex 0 -> 1, vertex 1 -> 2, vertex 2 -> 3, vertex 3 -> 2. No adjacent vertices share colors.

Example 2:

Input: V = 3, m = 2, E = 3, edges = [[0,1],[1,2],[0,2]] (Triangle / K3)
Output: false
Explanation: A complete 3-cycle requires at least 3 colors. Cannot be 2-colored.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master graph vertex coloring backtracking.
  • Implement vertex safety checks using adjacency representations.
  • Understand the connection between 2-coloring (Bipartite graphs in O(V+E)) vs M-coloring (NP-complete for M >= 3).

1. Brute Force All Color Combinations

Intuition

Iterate across all combinations from 11..1 to mm..m. For each full coloring, verify all E edges.

Algorithm

  1. Step 1: Assign each of the V vertices one of M colors from 1 to M.
  2. Step 2: When all V vertices have a color assigned (node == V), validate every edge (u, v).
  3. Step 3: If any edge connects two vertices of identical color, return false.
  4. Step 4: If all edges connect vertices of distinct colors, return true.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5public:
6 bool isValid(int v, const std::vector<std::vector<int>>& graph, const std::vector<int>& color) {
7 for (int i = 0; i < v; i++) {
8 for (int j = i + 1; j < v; j++) {
9 if (graph[i][j] && color[i] == color[j]) return false;
10 }
11 }
12 return true;
13 }
14
15 bool generateAll(int node, int v, int m, const std::vector<std::vector<int>>& graph, std::vector<int>& color) {
16 if (node == v) return isValid(v, graph, color);
17
18 for (int c = 1; c <= m; c++) {
19 color[node] = c;
20 if (generateAll(node + 1, v, m, graph, color)) return true;
21 }
22 return false;
23 }
24
25 bool graphColoring(int v, std::vector<std::pair<int, int>>& edges, int m) {
26 std::vector<std::vector<int>> graph(v, std::vector<int>(v, 0));
27 for (auto& e : edges) {
28 graph[e.first][e.second] = 1;
29 graph[e.second][e.first] = 1;
30 }
31 std::vector<int> color(v, 0);
32 return generateAll(0, v, m, graph, color);
33 }
34};
35
36int main() {
37 Solution solver;
38 std::vector<std::pair<int, int>> edges = {{0,1},{1,2},{2,3},{3,0},{0,2}};
39 std::cout << "Can color graph with 3 colors: " << (solver.graphColoring(4, edges, 3) ? "true" : "false") << "\n";
40 return 0;
41}

Time & Space Complexity

  • Time complexity: O(M^V * (V + E)) — Generates MV combinations and checks all E edges for each.
  • Space complexity: O(V) — O(V) for color assignment array.

2. Sequential Vertex Backtracking with Adjacency Matrix

Intuition

Function isSafe(node, c) checks if graph[node][i] == 1 && color[i] == c. If safe, set color[node] = c and recurse to node + 1.

Algorithm

  1. Step 1: Start at vertex 0 and define solve(node).
  2. Step 2: If node == V, all vertices are successfully colored; return true.
  3. Step 3: Try assigning colors c from 1 to M.
  4. Step 4: For each color c, call isSafe(node, c) by inspecting adjacency matrix row graph[node].
  5. Step 5: If safe, set color[node] = c and recurse on solve(node + 1). If successful, return true.
  6. Step 6: Backtrack by resetting color[node] = 0.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5public:
6 bool isSafe(int node, int c, int v, const std::vector<std::vector<int>>& graph, const std::vector<int>& color) {
7 for (int i = 0; i < v; i++) {
8 if (graph[node][i] && color[i] == c) return false;
9 }
10 return true;
11 }
12
13 bool solve(int node, int v, int m, const std::vector<std::vector<int>>& graph, std::vector<int>& color) {
14 if (node == v) return true;
15
16 for (int c = 1; c <= m; c++) {
17 if (isSafe(node, c, v, graph, color)) {
18 color[node] = c;
19 if (solve(node + 1, v, m, graph, color)) return true;
20 color[node] = 0;
21 }
22 }
23 return false;
24 }
25
26 bool graphColoring(int v, std::vector<std::pair<int, int>>& edges, int m) {
27 std::vector<std::vector<int>> graph(v, std::vector<int>(v, 0));
28 for (auto& e : edges) {
29 graph[e.first][e.second] = 1;
30 graph[e.second][e.first] = 1;
31 }
32 std::vector<int> color(v, 0);
33 return solve(0, v, m, graph, color);
34 }
35};
36
37int main() {
38 Solution solver;
39 std::vector<std::pair<int, int>> edges = {{0,1},{1,2},{2,3},{3,0},{0,2}};
40 std::cout << "M-Coloring result: " << (solver.graphColoring(4, edges, 3) ? "true" : "false") << "\n";
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(M^V) — Pruned backtracking tree visiting up to MV nodes.
  • Space complexity: O(V) — O(V) color array and recursion stack.

3. Backtracking with Adjacency List (Gold Standard)

Intuition

Iterating only over adj[node] reduces the per-node check overhead significantly, especially on sparse graphs. Early boolean propagation immediately exits the moment the final vertex V-1 is colored.

When to apply: Industry standard optimal solution: O(degree(v)) neighbor lookups via adjacency lists.

Algorithm

  1. Step 1: Convert edges into an adjacency list adj where adj[u] lists neighbors of u.
  2. Step 2: In solve(node), check if node == V; if so, return true.
  3. Step 3: Try colors c from 1 to M.
  4. Step 4: In isSafe(node, c), inspect only color[neighbor] for neighbor in adj[node] in O(degree(node)).
  5. Step 5: If valid, set color[node] = c and recurse on solve(node + 1).
  6. Step 6: Backtrack: unassign color[node] = 0. If no color works, return false.

Graph Coloring Decision Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Initialize graph with 4 uncolored vertices
Visual state
Values and pointers at this exact step
graph
V0
Color 1
V1
Uncolored
V2
Uncolored
V3
Uncolored

Node state shown; add connections to display graph edges.

Variables at this step
currentNode
0
colors
[1,0,0,0]
Check / comparison
Vertex 0 has no colored neighbors yet.
Decision / next transition
Assign Color 1 to Vertex 0. Recurse to Vertex 1.
Why this step matters

Initialize graph with 4 uncolored vertices. Start coloring from Vertex 0.

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5public:
6 bool isSafe(int node, int c, const std::vector<std::vector<int>>& adj, const std::vector<int>& color) {
7 for (int neighbor : adj[node]) {
8 if (color[neighbor] == c) return false;
9 }
10 return true;
11 }
12
13 bool solve(int node, int v, int m, const std::vector<std::vector<int>>& adj, std::vector<int>& color) {
14 if (node == v) return true;
15
16 for (int c = 1; c <= m; c++) {
17 if (isSafe(node, c, adj, color)) {
18 color[node] = c;
19 if (solve(node + 1, v, m, adj, color)) return true;
20 color[node] = 0;
21 }
22 }
23 return false;
24 }
25
26 bool graphColoring(int v, std::vector<std::pair<int, int>>& edges, int m) {
27 std::vector<std::vector<int>> adj(v);
28 for (auto& e : edges) {
29 adj[e.first].push_back(e.second);
30 adj[e.second].push_back(e.first);
31 }
32 std::vector<int> color(v, 0);
33 return solve(0, v, m, adj, color);
34 }
35};
36
37int main() {
38 Solution solver;
39 std::vector<std::pair<int, int>> edges = {{0,1},{1,2},{2,3},{3,0},{0,2}};
40 std::cout << "Optimal M-Coloring Result: " << (solver.graphColoring(4, edges, 3) ? "true" : "false") << "\n";
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(M^V) — Fastest recursive backtracking running with O(deg(u)) neighbor checks.
  • Space complexity: O(V + E) — O(V + E) memory for the adjacency list and color array.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force All Color AssignmentsO(M^V * V^2)O(V)Generate all MV possible colorings first, then validate the full graph.No early pruning
2.Backtracking with Adjacency Matrix (Better)O(M^V)O(V)Assign colors vertex by vertex, checking neighbors via adjacency matrix.Adjacency matrix iteration
3.Backtracking with Adjacency List & Degree Ordering (Optimal)OptimalO(M^V)O(V + E)Use adjacency lists for O(deg(v)) safety checks, exploring vertices in descending degree order.Graph chromatic number

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Not resetting color[node] = 0 when backtracking after a failed recursive branch.

Pitfall 2:

Using 0-indexed colors (1 to m is clearer so 0 unambiguously represents uncolored).

Crucial Edge Cases to Validate:

  • Complete graph Kn (requires exactly n colors): if m < n -> returns false.
  • Disconnected graph with independent components -> handled seamlessly.
  • Tree or Bipartite graph with m >= 2 -> always returns true.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State that 2-coloring is solvable in linear time O(V + E) using BFS/DFS Bipartite checking, whereas M >= 3 is NP-Complete.
  2. Highlight how Adjacency List reduces neighbor lookup from O(V) to O(degree).
  3. Mention Welsh-Powell or DSATUR greedy graph coloring heuristics if discussing real-world compiler register allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the computational complexity class of determining if a planar graph can be colored with 4 colors?

Back to DSA Sheet