Can a Graph Be Colored With at Most M Colors?
Solve this ProblemvertexCount vertices and a list of edges, plus a number of available colors m. Determine whether every vertex can be given one of the m colors so that no edge ever connects two same-colored vertices.
Assigning colors to every vertex first and validating the entire graph afterward finds the right answer, but a single bad choice made early on stays hidden until the whole coloring is complete and the full edge list gets scanned. Building each vertex's own list of neighbors up front turns that after-the-fact scan into a direct, immediate check — a color that conflicts with a vertex's own neighbors is ruled out before it's ever assigned, not discovered afterward by re-examining the whole graph.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ vertexCount ≤ 12 - ◆
0 ≤ edges.length ≤ vertexCount · (vertexCount − 1) / 2, each edge a pair of distinct vertex indices - ◆
1 ≤ m ≤ vertexCount - ◆
Two vertices joined by an edge may never share a color
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Assign All Colors First, Validate the Whole Graph After
BruteAssign every vertex a color from 1 to m, one at a time, without checking anything about its neighbors along the way — this tries all mⱽ possible colorings. Only once every vertex has a color does a separate pass scan the entire edge list to check whether any edge connects two same-colored vertices. This finds the right answer, but a coloring that violates its very first edge still gets completely filled in for every remaining vertex before that violation is ever noticed.
O(mᵛ · E)O(V)1class Solution {
2 public boolean canColorGraph(int vertexCount, int[][] edges, int m) {
3 int[] color = new int[vertexCount];
4 return tryAll(vertexCount, edges, m, 0, color);
5 }
6
7 private boolean tryAll(int vertexCount, int[][] edges, int m, int v, int[] color) {
8 if (v == vertexCount) {
9 return isValidColoring(edges, color);
10 }
11 for (int c = 1; c <= m; c++) {
12 color[v] = c;
13 if (tryAll(vertexCount, edges, m, v + 1, color)) return true;
14 }
15 return false;
16 }
17
18 private boolean isValidColoring(int[][] edges, int[] color) {
19 for (int[] edge : edges) {
20 if (color[edge[0]] == color[edge[1]]) return false;
21 }
22 return true;
23 }
24}Optimal — Check Each Vertex Against Its Own Neighbors Immediately
OptimalBuild an adjacency list once up front. Then, before assigning a color to a vertex, check it only against that vertex's own neighbors — a small, direct set, not the whole edge list — and only commit to a color that passes. If every color fails for the current vertex, backtrack immediately without ever touching the vertices after it. A conflict is caught at the exact vertex and color that caused it, not deferred to a scan of the finished (and already invalid) result.
O(mᵛ)O(V + E)1class Solution {
2 public boolean canColorGraph(int vertexCount, int[][] edges, int m) {
3 List<List<Integer>> adj = new ArrayList<>();
4 for (int i = 0; i < vertexCount; i++) adj.add(new ArrayList<>());
5 for (int[] edge : edges) {
6 adj.get(edge[0]).add(edge[1]);
7 adj.get(edge[1]).add(edge[0]);
8 }
9 int[] color = new int[vertexCount];
10 return backtrack(vertexCount, adj, m, 0, color);
11 }
12
13 private boolean backtrack(int vertexCount, List<List<Integer>> adj, int m, int v, int[] color) {
14 if (v == vertexCount) return true;
15 for (int c = 1; c <= m; c++) {
16 if (isSafe(v, c, adj, color)) {
17 color[v] = c;
18 if (backtrack(vertexCount, adj, m, v + 1, color)) return true;
19 color[v] = 0;
20 }
21 }
22 return false;
23 }
24
25 private boolean isSafe(int v, int c, List<List<Integer>> adj, int[] color) {
26 for (int neighbor : adj.get(v)) {
27 if (color[neighbor] == c) return false;
28 }
29 return true;
30 }
31}