Problem

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.

Examples

Example 1:

---
title: Input Graph
---

graph LR;
0 --- 1 & 2 & 3
1 --- 2
2 --- 3
  
---
title: Colored Graph
---

graph LR;
0 --- 1 & 2 & 3
1 --- 2
2 --- 3

style 0 fill:#FF9933
style 1 fill:#3399FF
style 3 fill:#3399FF
style 2 fill:#99FF33
  
Input: graph = [ 
	[ 0, 1, 1, 1 ],
	[ 1, 0, 1, 0 ],
	[ 1, 1, 0, 1 ],
	[ 1, 0, 1, 0 ],
]
Output: true

Solution

Method 1 - DFS

We can do following:

  • The is_graph_k_colorable function takes the adjacency matrix and the maximum number of colors (k) as input.
  • It initializes a list available_colors where each element represents a set of available colors for the corresponding vertex. Initially, all colors are available for each vertex.
  • The dfs function performs a recursive depth-first search to color the graph.
  • It checks available colors for the current vertex that are not assigned to any adjacent vertex.
  • It tries assigning a color to the current vertex and recursively tries coloring its neighbors with the next color (0-based indexing).
  • If coloring a neighbor fails (no available color), it backtracks by removing the assigned color from the current vertex’s available colors.
  • If all vertices are colored successfully, the function returns True. Otherwise, it returns False.
  • The main part calls dfs to start coloring from the first vertex with color 0.

Code

Java
public class GraphColoring {

	public static boolean isGraphKColorable(int[][] graph, int k) {
		int n = graph.length; // Number of vertices
		Set<Integer> [] availableColors = new HashSet[n];

		for (int i = 0; i < n; i++) {
			availableColors[i] = new HashSet<>();

			for (int color = 0; color < k; color++) {
				availableColors[i].add(color);
			}
		}

		return dfs(graph, 0, 0, availableColors);
	}

	private static boolean dfs(int[][] graph, int vertex, int assignedColor, Set<Integer> [] availableColors) {
		if (vertex == graph.length) {
			return true; // All vertices colored successfully
		}

		for (int neighbor = 0; neighbor < graph.length; neighbor++) {
			if (graph[vertex][neighbor] == 1 && availableColors[vertex].contains(assignedColor)) {
				availableColors[vertex].remove(assignedColor);

				if (dfs(graph, neighbor, assignedColor + 1, availableColors)) {
					return true;
				}

				availableColors[vertex].add(assignedColor);
			}
		}

		return false;
	}
}

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)