Graph coloring using greedy algorithm

Key takeaways:
Graph coloring is used to ensure that adjacent vertices in a graph have different colors, solving problems like scheduling and seating arrangements.
The greedy algorithm for graph coloring assigns the lowest available color to each vertex without considering global effects, which may lead to using more colors than necessary
The algorithm involves coloring vertices sequentially, checking adjacent nodes to avoid color conflicts.
The time complexity of the greedy algorithm is $O(V² + E)$ , where V is the number of vertices and E is the number of edges, while the space complexity is $O(V + E)$ .

Graph coloring, or vertex coloring, is a common problem in computer science where each vertex of a graph must be assigned a color such that no two adjacent vertices share the same color. This technique helps solve real-world problems like avoiding timetable clashes, optimizing schedules, allocating jobs, and managing team assignments or seating arrangements.

Example

A real-life scenario where we might want to use a graph coloring problem would be if we wanted to design a seating plan for a software development team. Suppose we want to seat 13 members, of which 2 members, Maverick and Minnie, abhor each other and don’t want to be seated together.

To reduce unwanted fights, the project manager might use the graph coloring greedy algorithm to solve this challenge.

Graph coloring using the greedy algorithm

Let’s look at how the greedy algorithm solves the graph coloring problem.

This algorithm does not guarantee the minimum number of colors needed. Instead, it assigns the lowest available color (smallest integer) to each vertex without considering the overall graph structure, making locally optimal choices at each step.

Because of this, the greedy approach may use more colors than necessary, especially in complex or irregular graphs.

However, it establishes an upper bound on the number of colors required. The algorithm will use at $most (degree of a vertex + 1)$ colors. This is because no vertex shares a color with its neighbors. The number of neighbors, or the vertex’s degree, limits how many colors may be needed.

First of all, we’ll color the first vertex with a color. Colors are labeled with numbers.
For the remaining vertices, we’ll repeat the following steps:
- Color the current vertex with a number that represents a color. Use the lowest number that hasn’t been used to color any previous adjacent graph nodes.
- We’ll ensure that if all previously used colors have been used to color the vertices adjacent to the current node, we’ll assign a new color to it.

Now, let’s look at the following illustration to get a better understanding of the solution:

def add_graph_edge(adjacency_list, node1, node2):	
	adjacency_list[node1].append(node2)
	adjacency_list[node2].append(node1) 
	return adjacency_list
graph_vertices = 5
graph = [[] for i in range(graph_vertices)]
graph = add_graph_edge(graph, 0, 1)
graph = add_graph_edge(graph, 0, 2)
graph = add_graph_edge(graph, 1, 2)
graph = add_graph_edge(graph, 1, 3)
graph = add_graph_edge(graph, 2, 3)
graph = add_graph_edge(graph, 3, 4)
def greedy_algorithm_for_graph_coloring(adjacency_list, graph_vertices):	
	final_colored_graph = [-1] * graph_vertices
	available_color = [False] * graph_vertices
	final_colored_graph[0] = 0
	for i in range(1, graph_vertices):
		for j in adjacency_list[i]:
			if final_colored_graph[j] != -1:
				available_color[final_colored_graph[j]] = True
		color_index = 0
		while color_index < graph_vertices:
			if available_color[color_index] != True:
				break
			
			color_index = color_index + 1
		final_colored_graph[i] = color_index 
		
		for i in adjacency_list[i]:
			if final_colored_graph[i] != -1:
				available_color[final_colored_graph[i]] = False
	
	return final_colored_graph
print("Colored graph")
final_colored_graph = greedy_algorithm_for_graph_coloring(graph, graph_vertices)
for i in range(graph_vertices):
    print(f"Vertex  {i}  has color {final_colored_graph[i]}")

Code explanation

Lines 1–4: Firstly, we define a function add_graph_edge that receives two nodes and creates an edge between the two.
Lines 6–13: Next, we create a graph with 5 vertices. We also create edges between adjacent vertices.
Lines 16–19: We go on to define a function called greedy_algorithm_for_graph_coloring. It receives the graphs adjacency_list and the total vertices in the graph. We initialize two lists: final_colored_graph and available_color and populate them with -1 and False respectively. We also set the first vertex to be colored with the first color; this color is numbered with the number 0.
Lines 21–24: We will then iterate over the remaining nodes and mark their colors as unavailable.
Lines 26–32: In this code section, we will find the first available color and assign that color to the current vertex.
Lines 34–38: Then we rest the values back to False for the next iteration.
Lines 40–43: Lastly, we call the greedy function, passing it the graph we created previously. We print the vertices and the colors assigned to them.

Time complexity

The greedy_algorithm_for_graph_coloring function has a time complexity of $O(V^2+E)$ .

It iterates through each vertex $V$ , with each vertex's adjacency list requiring traversal of all $E$ edges. Additionally, finding the available color and updating colors involves scanning and updating arrays, leading to a dominant term of $O(V^2)$ for the coloring process.

Combining them, the time complexity of this approach is ${O(V^2 + E)}$ .

Space complexity

The additional space used by greedy_algorithm_for_graph_coloring is proportional to the number of vertices $V$ . Therefore, while the function itself operates with $O(1)$ space complexity regarding temporary variables, the total space complexity considering the input structures is $O(V+E)$

Free AI Mock Interviews

Coding Interview

Coding PatternsFree Interview

Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.

System Design

YouTubeFree Interview

Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.