Day 52: Graph Coloring

Table of Contents

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:

def graph_coloring(graph):
    # Sort vertices in descending order of degree
    vertices = sorted(graph, key=lambda x: len(graph[x]), reverse=True)
    color_map = {}

    for vertex in vertices:
        # Find the first available color
        used_colors = set(color_map.get(neighbor) for neighbor in graph[vertex] if neighbor in color_map)
        color_map[vertex] = next(color for color in range(len(vertices)) if color not in used_colors)

    return color_map

def print_coloring(color_map):
    print("Vertex : Color")
    for vertex, color in color_map.items():
        print(f"{vertex} : {color}")

# Example usage
graph = {
    0: [1, 2, 3],
    1: [0, 2],
    2: [0, 1, 3],
    3: [0, 2]
}

coloring = graph_coloring(graph)
print_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:

def graph_coloring_backtrack(graph, m):
    def is_safe(v, color, c):
        for i in graph[v]:
            if color[i] == c:
                return False
        return True

    def color_util(m, color, v):
        if v == len(graph):
            return True

        for c in range(1, m + 1):
            if is_safe(v, color, c):
                color[v] = c
                if color_util(m, color, v + 1):
                    return True
                color[v] = 0

    color = [0] * len(graph)
    if color_util(m, color, 0):
        return color
    return None

# Example usage
graph = {
    0: [1, 2, 3],
    1: [0, 2],
    2: [0, 1, 3],
    3: [0, 2]
}

m = 3  # Number of colors
result = graph_coloring_backtrack(graph, m)
if result:
    print("Coloring possible with", m, "colors:")
    print("Vertex : Color")
    for vertex, color in enumerate(result):
        print(f"{vertex} : {color}")
else:
    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!