Log inSign up
hardGeeksforGeeksNot Started

Graph Coloring

Given an undirected graph with V vertices and E edges, find a valid assignment of colors to vertices such that no two adjacent vertices share the same color, using the minimum number of colors (chromatic number).

Graph
Solve on GeeksforGeeks
Lesson

Problem Statement

### Problem Statement

Given an undirected graph with V vertices numbered 0 to V - 1 and an adjacency list adj.

Assign a color to each vertex such that no two adjacent vertices share the same color.

Your goal is to color the graph using the minimum possible number of colors (known as the chromatic number χ(G)), or determine if a valid coloring exists using at most M colors. Return the color array color of length V where color[i] is an integer in [0, M - 1]. If no valid assignment exists within M colors, return [].

---

### Examples

Example 1: ``text Input: V = 4, adj = [[1, 2, 3], [0, 2], [0, 1, 3], [0, 2]], M = 3 Output: [0, 1, 2, 1] Explanation: - Node 0 has color 0. - Node 1 (connected to 0, 2) has color 1. - Node 2 (connected to 0, 1, 3) has color 2. - Node 3 (connected to 0, 2) can take color 1 (same as node 1, since 1 and 3 are not adjacent). No two adjacent nodes share the same color. 3 colors are sufficient.

Example 2 (Complete Graph K4): ``text Input: V = 4 (all pairs connected), M = 3 Output: [] Explanation: A complete graph with 4 vertices requires 4 distinct colors. It cannot be colored with M = 3 colors.

---

### Constraints - 1 <= V <= 50 - 1 <= M <= V - 0 <= adj[i].length < V - Undirected graph with no self-loops.

Constraints:

  • 1 <= V <= 50
  • 1 <= M <= V
  • 0 <= E <= V * (V - 1) / 2

What You'll Learn

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

  • Distinguish between 2-coloring (Bipartite, polynomial) and M-coloring (NP-complete for M >= 3).
  • Implement the classic Backtracking algorithm for M-coloring.
  • Understand the Welsh-Powell greedy ordering heuristic.
  • Apply constraint propagation to prune invalid branches early.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Register allocation in compiler optimization.
  • Exam timetable scheduling (no two conflicting exams at the same time slot).
  • Frequency assignment in wireless networks without signal interference.

Algorithmic Decision Tree:

  • If M = 2 colors -> Check if graph is Bipartite using BFS/DFS in O(V + E).
  • If M >= 3 colors -> NP-complete; use Backtracking with Degree Heuristic or Welsh-Powell greedy.

Connected Patterns:

Bipartite GraphSudoku SolverN-Queens Problem

1. All M^V Color Configurations Enumeration

Intuition

Generate all MV possible color assignments using recursion. Check each complete configuration for edge conflicts.

Algorithm

  1. Recursively assign every possible color 0 to M - 1 to each vertex from 0 to V - 1.
  2. When all V vertices have a color assigned:
  3. Check every edge (u, v): if color[u] == color[v], configuration is invalid.
  4. If all edges valid, return the configuration.
  5. If no configuration satisfies the condition, return false.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6bool isValid(const vector<vector<int>>& edges, const vector<int>& color) {
7 for (const auto& e : edges) {
8 if (color[e[0]] == color[e[1]]) return false;
9 }
10 return true;
11}
12
13bool generateAll(int u, int V, int M, const vector<vector<int>>& edges, vector<int>& color) {
14 if (u == V) {
15 return isValid(edges, color);
16 }
17
18 for (int c = 0; c < M; ++c) {
19 color[u] = c;
20 if (generateAll(u + 1, V, M, edges, color)) return true;
21 }
22 return false;
23}
24
25int main() {
26 int V = 4, M = 3;
27 vector<vector<int>> edges = {{0, 1}, {0, 2}, {0, 3}, {1, 2}, {2, 3}};
28 vector<int> color(V, -1);
29
30 if (generateAll(0, V, M, edges, color)) {
31 cout << "Color assignment: ";
32 for (int c : color) cout << c << " ";
33 cout << endl;
34 } else {
35 cout << "No valid coloring found" << endl;
36 }
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(M^V * E)
  • Space complexity: O(V)

2. Greedy Vertex Coloring (Welsh-Powell Heuristic)

Intuition

Sort vertices by degree descending. For each vertex, assign the lowest non-conflicting color. Guaranteed polynomial time O(V2 + E).

Algorithm

  1. Initialize color array with -1 for all vertices.
  2. Assign color 0 to vertex 0.
  3. For vertex u from 1 to V - 1:
  4. Mark colors of all already-colored adjacent neighbors as unavailable.
  5. Find the lowest color index c >= 0 that is available.
  6. Set color[u] = c.
  7. Return color array.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7vector<int> greedyColoring(int V, const vector<vector<int>>& adj) {
8 vector<int> color(V, -1);
9 color[0] = 0; // First vertex gets color 0
10
11 vector<bool> available(V, true);
12
13 for (int u = 1; u < V; ++u) {
14 // Mark colors of adjacent vertices as unavailable
15 for (int v : adj[u]) {
16 if (color[v] != -1) {
17 available[color[v]] = false;
18 }
19 }
20
21 // Find the first available color
22 int cr = 0;
23 for (; cr < V; ++cr) {
24 if (available[cr]) break;
25 }
26
27 color[u] = cr;
28
29 // Reset available flags for next vertex
30 for (int v : adj[u]) {
31 if (color[v] != -1) {
32 available[color[v]] = true;
33 }
34 }
35 }
36 return color;
37}
38
39int main() {
40 int V = 4;
41 vector<vector<int>> adj = {{1, 2, 3}, {0, 2}, {0, 1, 3}, {0, 2}};
42 auto res = greedyColoring(V, adj);
43 cout << "Greedy Colors: ";
44 for (int c : res) cout << c << " ";
45 cout << endl;
46 return 0;
47}

Time & Space Complexity

  • Time complexity: O(V^2 + E)
  • Space complexity: O(V)

3. Backtracking with Forward Pruning (Exact M-Coloring)

Intuition

Assign colors recursively from 0 to M - 1. Prune immediately when a color conflicts with an already-colored adjacent neighbor.

Algorithm

  1. Define helper isSafe(u, c): returns false if any neighbor v of u has color[v] == c.
  2. In solve(u):
  3. If u == V: all vertices successfully colored, return true.
  4. For each color c from 0 to M - 1:
  5. If isSafe(u, c):
  6. Set color[u] = c.
  7. If solve(u + 1) == true: return true.
  8. Set color[u] = -1 (backtrack).
  9. Return false.
  10. If solve(0) succeeds, return color; else return [].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class GraphColoring {
7 int V, M;
8 vector<vector<int>> adj;
9 vector<int> color;
10
11 bool isSafe(int u, int c) {
12 for (int v : adj[u]) {
13 if (color[v] == c) return false;
14 }
15 return true;
16 }
17
18 bool solve(int u) {
19 if (u == V) return true; // All vertices colored
20
21 for (int c = 0; c < M; ++c) {
22 if (isSafe(u, c)) {
23 color[u] = c;
24 if (solve(u + 1)) return true;
25 color[u] = -1; // Backtrack
26 }
27 }
28 return false;
29 }
30
31public:
32 GraphColoring(int v, int m, const vector<vector<int>>& edges) : V(v), M(m), adj(v), color(v, -1) {
33 for (const auto& e : edges) {
34 adj[e[0]].push_back(e[1]);
35 adj[e[1]].push_back(e[0]);
36 }
37 }
38
39 vector<int> colorGraph() {
40 if (solve(0)) return color;
41 return {};
42 }
43};
44
45int main() {
46 int V = 4, M = 3;
47 vector<vector<int>> edges = {{0, 1}, {0, 2}, {0, 3}, {1, 2}, {2, 3}};
48 GraphColoring solver(V, M, edges);
49 auto res = solver.colorGraph();
50
51 if (!res.empty()) {
52 cout << "Optimal Colors: ";
53 for (int c : res) cout << c << " ";
54 cout << endl;
55 } else {
56 cout << "No valid coloring" << endl;
57 }
58 return 0;
59}

Time & Space Complexity

  • Time complexity: O(M^V) worst case, highly pruned in practice
  • Space complexity: O(V)

Approach Comparison Matrix

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

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Exhaustive MV EnumerationO(M^V * E)O(V)Generate all MV possible color assignments and verify if all edges satisfy color[u] != color[v].Unpruned combinatorial search.
2.Greedy Vertex Coloring (Welsh-Powell)O(V^2 + E)O(V)Order vertices by descending degree. Greedily assign the lowest available non-conflicting color.Local greedy choice lacks global foresight.
3.Backtracking with Pruning & Degree Ordering (Optimal Exact)OptimalO(M^V) worst-case, heavily pruned in practiceO(V)Assign colors recursively. Immediately prune any color that conflicts with an assigned neighbor.Exhaustive branch search when no valid M-coloring exists.

Common Pitfalls & Crucial Edge Cases

Assuming greedy coloring finds the chromatic number

Greedy coloring guarantees an upper bound of Δ + 1, not the minimum.

Not checking all neighbors in isSafe()

Only checking the parent or previous vertex rather than all adjacent nodes.

Index confusion with 1-based vs 0-based colors

Use colors 0 to M - 1 or 1 to M consistently.

Crucial Edge Cases to Validate:

  • Graph with 0 edges — Every vertex can take color 0; requires 1 color.
  • Complete Graph K_V — Requires exactly V colors.
  • Bipartite Graph (e.g. Tree, Even Cycle) — Requires exactly 2 colors.
  • Odd Cycle C_5 — Requires exactly 3 colors.

Interview Tips & Best Practices

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

  1. Mention the 4-Color Theorem: Every planar graph can be colored using at most 4 colors.
  2. Relate graph coloring to register allocation in optimizing compilers (Chaitin's algorithm).
  3. Explain the distinction between finding the chromatic number (optimization) and decision M-coloring.

Quick Comprehension Check

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

1.Why is 2-Coloring solvable in linear O(V + E) time, while 3-Coloring is NP-Complete?

2.What does Brook's Theorem state regarding graph coloring?

Back to DSA Sheet