Find Chromatic Number in Python
Find the chromatic number of a given graph G, which is the smallest number of colors needed to color the vertices of the graph in such a way that no two adjacent vertices share the same color.
Examples:
Input: Vertices = 5, Edges: [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (3, 4)]
Output: Chromatic Number: 3Input: Vertices = 4, Edges: [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3)]
Output: Chromatic Number: 2
Chromatic Number in Python Using Greedy Algorithm:
Assign colors to vertices of the graph in the order of their degrees. Always assign the smallest possible color that hasn’t been used by its neighbors.
Steps-by-step algorithm:
- Initialize an empty dictionary
color_map
to store the color of each vertex. - Sort the vertices based on their degrees in non-increasing order.
- For each vertex, assign the smallest possible color that hasn’t been used by its neighbors.
- Return the number of unique colors used.
Below is the implementation of the above approach:
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = [[] for _ in range(vertices)]
def add_edge(self, u, v):
self.graph[u].append(v)
self.graph[v].append(u)
def greedy_coloring(self):
color_map = {}
# Sort vertices by their degrees in non-increasing order
vertices_degrees = [(len(self.graph[i]), i) for i in range(self.V)]
vertices_degrees.sort(reverse=True)
# Assign colors to vertices
for _, vertex in vertices_degrees:
neighbor_colors = {color_map.get(neigh) for neigh in self.graph[vertex]}
color_map[vertex] = next(color for color in range(self.V) if color not in neighbor_colors)
# Return the number of unique colors used
return len(set(color_map.values()))
# Example Usage
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)
g.add_edge(3, 4)
print(g.greedy_coloring()) # Output: 3
Output
3
Time Complexity: O(V+E), where V is the number of vertices and E is the number of edges.
Auxiliary Space: O(V) for the color map dictionary.
Find Chromatic Number in Python Using Backtracking Algorithm:
Use a backtracking approach to try different colorings recursively, keeping track of the chromatic number.
Step-by-step algorithm:
- Define a recursive function
color_graph
that tries to color the graph using a given number of colors. - For each vertex, try coloring it with each available color.
- If a coloring is found where no two adjacent vertices share the same color, recursively try to color the remaining vertices.
- Return the minimum number of colors needed to color the graph.
Below is the implementation of the above approach:
class Graph:
# Constructor to intialize the graph
def __init__(self, vertices):
self.V = vertices
self.graph = [[] for _ in range(vertices)]
# Function to add an undirected edge in Python
def add_edge(self, u, v):
self.graph[u].append(v)
self.graph[v].append(u)
# Function to check whether it is safe to color the vertex
# with the given color such that none of the eighbor has the same color
def is_safe(self, vertex, color, color_map):
for neighbor in self.graph[vertex]:
if color_map.get(neighbor) == color:
return False
return True
# Function to color the graph with num_colors
def color_graph(self, vertex, num_colors, color_map):
if vertex == self.V:
return True
for color in range(num_colors):
if self.is_safe(vertex, color, color_map):
color_map[vertex] = color
if self.color_graph(vertex + 1, num_colors, color_map):
return True
color_map[vertex] = -1
return False
# Function to find the chromatic number of the graph
def backtracking_coloring(self):
# Initialize color map with -1 for uncolored vertices
color_map = {-1: -1}
num_colors = 1
while not self.color_graph(0, num_colors, color_map):
num_colors += 1
color_map = {-1: -1}
return num_colors
# Example Usage
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)
g.add_edge(3, 4)
print(g.backtracking_coloring()) # Output: 3
Output
3
Time Complexity: Exponential, O(kn), where k is the number of colors and n is the number of vertices.
Auxiliary Space: O(n) for the recursion stack and the color map dictionary.
Contact Us