Find Chromatic Number in Python Using Backtracking Algorithm

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