Day 52: Graph Coloring#

Welcome to Day 52 of our 60 Days of Coding Algorithm Challenge! Today, we’ll explore the Graph Coloring problem, a fundamental problem in graph theory with numerous practical applications.

What is Graph Coloring?#

Graph coloring is the assignment of labels (colors) to elements of a graph subject to certain constraints. In its simplest form, it’s the task of assigning a color to each vertex of a graph so that no two adjacent vertices share the same color.

Understanding the Problem#

• We have an undirected graph G = (V, E), where V is the set of vertices and E is the set of edges.
• We need to assign colors to vertices such that no two adjacent vertices have the same color.
• The goal is typically to use the minimum number of colors possible (known as the chromatic number of the graph).

Greedy Approach#

We’ll start with a simple greedy approach to solve this problem:

1. Sort the vertices in descending order of degree (number of neighbors).
2. Assign the first color to the first vertex.
3. For the remaining vertices, consider the currently assigned colors:
   • Assign the smallest numbered color that has not been assigned to any neighbors.
   • If all previously used colors are assigned to neighbors, assign a new color.

Implementation#

Here’s a Python implementation of the Graph Coloring problem using a greedy approach:

 1def graph_coloring(graph):
 2    # Sort vertices in descending order of degree
 3    vertices = sorted(graph, key=lambda x: len(graph[x]), reverse=True)
 4    color_map = {}
 5
 6    for vertex in vertices:
 7        # Find the first available color
 8        used_colors = set(color_map.get(neighbor) for neighbor in graph[vertex] if neighbor in color_map)
 9        color_map[vertex] = next(color for color in range(len(vertices)) if color not in used_colors)
10
11    return color_map
12
13def print_coloring(color_map):
14    print("Vertex : Color")
15    for vertex, color in color_map.items():
16        print(f"{vertex} : {color}")
17
18# Example usage
19graph = {
20    0: [1, 2, 3],
21    1: [0, 2],
22    2: [0, 1, 3],
23    3: [0, 2]
24}
25
26coloring = graph_coloring(graph)
27print_coloring(coloring)

Time Complexity#

The time complexity of this greedy algorithm is O(V^2 + E), where V is the number of vertices and E is the number of edges. This comes from sorting the vertices (O(V log V)), and then for each vertex, checking its neighbors (total O(V + E)).

Space Complexity#

The space complexity is O(V) to store the color assignments.

Backtracking Approach#

While the greedy approach is fast, it doesn’t guarantee using the minimum number of colors. For that, we can use a backtracking approach:

 1def graph_coloring_backtrack(graph, m):
 2    def is_safe(v, color, c):
 3        for i in graph[v]:
 4            if color[i] == c:
 5                return False
 6        return True
 7
 8    def color_util(m, color, v):
 9        if v == len(graph):
10            return True
11
12        for c in range(1, m + 1):
13            if is_safe(v, color, c):
14                color[v] = c
15                if color_util(m, color, v + 1):
16                    return True
17                color[v] = 0
18
19    color = [0] * len(graph)
20    if color_util(m, color, 0):
21        return color
22    return None
23
24# Example usage
25graph = {
26    0: [1, 2, 3],
27    1: [0, 2],
28    2: [0, 1, 3],
29    3: [0, 2]
30}
31
32m = 3  # Number of colors
33result = graph_coloring_backtrack(graph, m)
34if result:
35    print("Coloring possible with", m, "colors:")
36    print("Vertex : Color")
37    for vertex, color in enumerate(result):
38        print(f"{vertex} : {color}")
39else:
40    print("Coloring not possible with", m, "colors")

This backtracking approach has a time complexity of O(m^V), where m is the number of colors and V is the number of vertices.

Applications of Graph Coloring#

1. Map Coloring
2. Register Allocation in compilers
3. Radio Frequency Assignment
4. Sudoku Puzzle Solving
5. Scheduling Problems

Variations of the Problem#

1. Edge Coloring: Assign colors to edges instead of vertices.
2. List Coloring: Each vertex has a list of allowed colors.
3. Total Coloring: Color both vertices and edges.

Exercise#

1. Implement a function to determine the chromatic number of a graph (minimum number of colors needed).
2. Solve the Map Coloring problem for a given map using graph coloring techniques.
3. Implement the Welsh-Powell algorithm for graph coloring and compare its performance with the greedy and backtracking approaches.

Summary#

Today, we explored the Graph Coloring problem, a fundamental problem in graph theory with numerous practical applications. We implemented both greedy and backtracking solutions, discussed their time and space complexities, and looked at variations and applications of the problem.

Graph coloring is an NP-complete problem, meaning there’s no known polynomial-time algorithm that can optimally color any graph. However, the techniques we’ve learned today are valuable for solving many real-world problems and form the basis for more advanced graph algorithms.

Tomorrow, we’ll dive into Bit Manipulation Techniques, exploring how to efficiently perform operations at the bit level. Stay tuned!

Solution#

 1# Exercise 1: Determine the chromatic number (minimum colors) of a graph.
 2# We try m = 1, 2, 3, ... and return the first m that admits a valid coloring.
 3def is_m_colorable(graph, m):
 4    color = {v: 0 for v in graph}
 5
 6    def is_safe(v, c):
 7        return all(color[nb] != c for nb in graph[v])
 8
 9    vertices = list(graph)
10
11    def assign(i):
12        if i == len(vertices):
13            return True
14        v = vertices[i]
15        for c in range(1, m + 1):
16            if is_safe(v, c):
17                color[v] = c
18                if assign(i + 1):
19                    return True
20                color[v] = 0  # Backtrack.
21        return False
22
23    return assign(0)
24
25def chromatic_number(graph):
26    for m in range(1, len(graph) + 1):
27        if is_m_colorable(graph, m):
28            return m
29    return len(graph)  # A graph is always |V|-colorable.
30
31graph = {
32    0: [1, 2, 3],
33    1: [0, 2],
34    2: [0, 1, 3],
35    3: [0, 2],
36}
37print("Chromatic number:", chromatic_number(graph))  # 3