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_mapto 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
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
Contact Us