Graph Coloring and K-Coloring: A Comprehensive Guide

# Adjacency list representation
graph = {
    'A': ['B', 'D'],
    'B': ['A', 'C'],
    'C': ['B', 'D'],
    'D': ['A', 'C']
}

# Adjacency matrix representation (for 4 vertices)
# 0=A, 1=B, 2=C, 3=D
graph_matrix = [
    [0, 1, 0, 1],  # A connects to B and D
    [1, 0, 1, 0],  # B connects to A and C
    [0, 1, 0, 1],  # C connects to B and D
    [1, 0, 1, 0]   # D connects to A and C
]

// JavaScript adjacency list
const graph = new Map([
    ['A', ['B', 'D']],
    ['B', ['A', 'C']],
    ['C', ['B', 'D']],
    ['D', ['A', 'C']]
]);

def is_proper_coloring(graph, coloring):
    """
    Check if a coloring is valid (proper).
    
    Args:
        graph: dict mapping vertices to lists of neighbors
        coloring: dict mapping vertices to colors
    
    Returns:
        bool: True if coloring is proper, False otherwise
    """
    for vertex in graph:
        vertex_color = coloring.get(vertex)
        for neighbor in graph[vertex]:
            neighbor_color = coloring.get(neighbor)
            if vertex_color == neighbor_color:
                return False
    return True

# Example usage
graph = {
    'A': ['B', 'D'],
    'B': ['A', 'C'],
    'C': ['B', 'D'],
    'D': ['A', 'C']
}

coloring = {'A': 1, 'B': 2, 'C': 1, 'D': 2}
print(is_proper_coloring(graph, coloring))  # True

bad_coloring = {'A': 1, 'B': 1, 'C': 2, 'D': 2}
print(is_proper_coloring(graph, bad_coloring))  # False (A and B are adjacent)

# Complete graph K4
k4_graph = {
    'A': ['B', 'C', 'D'],
    'B': ['A', 'C', 'D'],
    'C': ['A', 'B', 'D'],
    'D': ['A', 'B', 'C']
}

# Only valid coloring uses 4 distinct colors
k4_coloring = {'A': 1, 'B': 2, 'C': 3, 'D': 4}

def can_color_with_k_colors(graph, k):
    """
    Determine if graph can be colored with k colors.
    
    Args:
        graph: dict mapping vertices to lists of neighbors
        k: number of colors available
    
    Returns:
        tuple: (bool, dict) - (is_colorable, coloring)
    """
    vertices = list(graph.keys())
    coloring = {}
    
    def is_safe(vertex, color):
        """Check if assigning color to vertex is safe."""
        for neighbor in graph[vertex]:
            if coloring.get(neighbor) == color:
                return False
        return True
    
    def backtrack(vertex_idx):
        """Recursively try to color vertices."""
        if vertex_idx == len(vertices):
            return True  # All vertices colored
        
        vertex = vertices[vertex_idx]
        for color in range(1, k + 1):
            if is_safe(vertex, color):
                coloring[vertex] = color
                if backtrack(vertex_idx + 1):
                    return True
                del coloring[vertex]  # Backtrack
        
        return False
    
    success = backtrack(0)
    return success, coloring if success else {}

# Example: Test if square graph can be colored with 2 colors
square_graph = {
    'A': ['B', 'D'],
    'B': ['A', 'C'],
    'C': ['B', 'D'],
    'D': ['A', 'C']
}

can_color, coloring = can_color_with_k_colors(square_graph, 2)
print(f"Can color with 2 colors: {can_color}")  # True
print(f"Coloring: {coloring}")  # {'A': 1, 'B': 2, 'C': 1, 'D': 2}

# Test with K4 (complete graph)
k4_graph = {
    'A': ['B', 'C', 'D'],
    'B': ['A', 'C', 'D'],
    'C': ['A', 'B', 'D'],
    'D': ['A', 'B', 'C']
}

can_color_3, _ = can_color_with_k_colors(k4_graph, 3)
print(f"K4 with 3 colors: {can_color_3}")  # False

can_color_4, coloring_4 = can_color_with_k_colors(k4_graph, 4)
print(f"K4 with 4 colors: {can_color_4}")  # True
print(f"Coloring: {coloring_4}")  # {'A': 1, 'B': 2, 'C': 3, 'D': 4}

def find_chromatic_number(graph):
    """
    Find the chromatic number of a graph.
    
    Args:
        graph: dict mapping vertices to lists of neighbors
    
    Returns:
        int: chromatic number
    """
    n = len(graph)
    for k in range(1, n + 1):
        can_color, _ = can_color_with_k_colors(graph, k)
        if can_color:
            return k
    return n  # Worst case: complete graph

# Examples
print(f"Square graph χ(G) = {find_chromatic_number(square_graph)}")  # 2
print(f"K4 graph χ(G) = {find_chromatic_number(k4_graph)}")  # 4

def solve_exam_scheduling():
    """Complete exam scheduling example."""
    # Student enrollments
    enrollments = {
        'M': {1, 2, 3, 4},
        'P': {2, 3, 5},
        'C': {1, 4, 6},
        'B': {3, 5, 6},
        'E': {1, 2},
        'H': {4, 5, 6}
    }
    
    # Build conflict graph
    exams = list(enrollments.keys())
    graph = {exam: [] for exam in exams}
    
    for i, exam1 in enumerate(exams):
        for exam2 in exams[i+1:]:
            # Check if exams share students
            if enrollments[exam1] & enrollments[exam2]:
                graph[exam1].append(exam2)
                graph[exam2].append(exam1)
    
    print("Conflict graph:")
    for exam, conflicts in graph.items():
        print(f"  {exam}: {conflicts}")
    
    # Apply Welsh-Powell
    schedule = welsh_powell_coloring(graph)
    
    print("\nExam Schedule:")
    slots = {}
    for exam, slot in schedule.items():
        if slot not in slots:
            slots[slot] = []
        slots[slot].append(exam)
    
    for slot in sorted(slots.keys()):
        print(f"  Slot {slot}: {', '.join(slots[slot])}")
    
    print(f"\nTotal slots needed: {max(schedule.values())}")
    
    # Verify no conflicts
    print("\nVerification:")
    for exam1, slot1 in schedule.items():
        for exam2, slot2 in schedule.items():
            if exam1 < exam2 and slot1 == slot2:
                shared = enrollments[exam1] & enrollments[exam2]
                if shared:
                    print(f"  ERROR: {exam1} and {exam2} conflict!")
                else:
                    print(f"  OK: {exam1} and {exam2} in same slot (no shared students)")

solve_exam_scheduling()

def edge_coloring_to_vertex_coloring(graph):
    """
    Convert edge coloring to vertex coloring problem.
    Create line graph where edges become vertices.
    
    Args:
        graph: dict mapping vertices to lists of neighbors
    
    Returns:
        dict: line graph for edge coloring
    """
    # Create edges list
    edges = []
    for vertex in graph:
        for neighbor in graph[vertex]:
            edge = tuple(sorted([vertex, neighbor]))
            if edge not in edges:
                edges.append(edge)
    
    # Build line graph: vertices are edges, edges connect adjacent edges
    line_graph = {i: [] for i in range(len(edges))}
    
    for i, edge1 in enumerate(edges):
        for j, edge2 in enumerate(edges):
            if i != j:
                # Edges are adjacent if they share a vertex
                if edge1[0] in edge2 or edge1[1] in edge2:
                    line_graph[i].append(j)
    
    return line_graph, edges

# Example
graph = {'A': ['B', 'C'], 'B': ['A', 'C'], 'C': ['A', 'B']}
line_graph, edges = edge_coloring_to_vertex_coloring(graph)
print(f"Original edges: {edges}")
print(f"Line graph: {line_graph}")

# Color the line graph
coloring = greedy_coloring(line_graph)
print(f"Edge coloring: {coloring}")

def list_coloring(graph, color_lists):
    """
    Color graph where each vertex has allowed colors.
    
    Args:
        graph: dict mapping vertices to neighbors
        color_lists: dict mapping vertices to lists of allowed colors
    
    Returns:
        tuple: (success, coloring or None)
    """
    vertices = list(graph.keys())
    coloring = {}
    
    def is_safe(vertex, color):
        """Check if color is valid for vertex."""
        if color not in color_lists[vertex]:
            return False
        for neighbor in graph[vertex]:
            if coloring.get(neighbor) == color:
                return False
        return True
    
    def backtrack(idx):
        """Try to color vertices with list constraints."""
        if idx == len(vertices):
            return True
        
        vertex = vertices[idx]
        for color in color_lists[vertex]:
            if is_safe(vertex, color):
                coloring[vertex] = color
                if backtrack(idx + 1):
                    return True
                del coloring[vertex]
        
        return False
    
    success = backtrack(0)
    return success, coloring if success else None

# Example: Vertices have restricted color choices
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'C'],
    'C': ['A', 'B']
}

color_lists = {
    'A': [1, 2],      # A can only be color 1 or 2
    'B': [2, 3],      # B can only be color 2 or 3
    'C': [1, 3]       # C can only be color 1 or 3
}

success, coloring = list_coloring(graph, color_lists)
print(f"List coloring success: {success}")
print(f"Coloring: {coloring}")

def chromatic_polynomial_deletion_contraction(graph, k, memo=None):
    """
    Compute chromatic polynomial using deletion-contraction.
    P(G, k) = P(G-e, k) - P(G/e, k)
    
    Args:
        graph: dict mapping vertices to neighbors
        k: number of colors
        memo: memoization dict
    
    Returns:
        int: number of valid k-colorings
    """
    if memo is None:
        memo = {}
    
    # Convert graph to hashable form for memoization
    graph_key = tuple(sorted((v, tuple(sorted(neighbors))) 
                            for v, neighbors in graph.items()))
    
    if (graph_key, k) in memo:
        return memo[(graph_key, k)]
    
    # Base cases
    if not graph:
        return 1
    
    # If no edges, each vertex can be any of k colors
    total_edges = sum(len(neighbors) for neighbors in graph.values()) // 2
    if total_edges == 0:
        result = k ** len(graph)
        memo[(graph_key, k)] = result
        return result
    
    # Find an edge to delete/contract
    for vertex in graph:
        if graph[vertex]:
            neighbor = graph[vertex][0]
            
            # Deletion: remove edge
            graph_minus_e = {v: [n for n in neighbors if not (v == vertex and n == neighbor) 
                                                        and not (v == neighbor and n == vertex)]
                            for v, neighbors in graph.items()}
            
            # Contraction: merge vertices
            graph_contract_e = {}
            for v in graph:
                if v == neighbor:
                    continue
                new_neighbors = []
                for n in graph[v]:
                    if n == neighbor:
                        new_neighbors.append(vertex)
                    elif n != vertex:
                        new_neighbors.append(n)
                if v == vertex:
                    new_neighbors.extend([n for n in graph[neighbor] if n != vertex])
                graph_contract_e[v] = list(set(new_neighbors))
            
            result = (chromatic_polynomial_deletion_contraction(graph_minus_e, k, memo) -
                     chromatic_polynomial_deletion_contraction(graph_contract_e, k, memo))
            
            memo[(graph_key, k)] = result
            return result
    
    return 0

# Example: Count 3-colorings of a triangle
triangle = {
    'A': ['B', 'C'],
    'B': ['A', 'C'],
    'C': ['A', 'B']
}

for k in range(1, 6):
    count = chromatic_polynomial_deletion_contraction(triangle, k)
    print(f"P(triangle, {k}) = {count}")
# Expected: 0, 0, 6, 24, 60 (formula: k(k-1)(k-2))

def precoloring_extension(graph, precolored, k):
    """
    Extend a partial coloring to full coloring.
    
    Args:
        graph: dict mapping vertices to neighbors
        precolored: dict of already colored vertices
        k: maximum colors allowed
    
    Returns:
        tuple: (success, full coloring or None)
    """
    coloring = precolored.copy()
    uncolored = [v for v in graph if v not in precolored]
    
    def is_safe(vertex, color):
        """Check if color is valid."""
        for neighbor in graph[vertex]:
            if coloring.get(neighbor) == color:
                return False
        return True
    
    def backtrack(idx):
        """Try to color remaining vertices."""
        if idx == len(uncolored):
            return True
        
        vertex = uncolored[idx]
        for color in range(1, k + 1):
            if is_safe(vertex, color):
                coloring[vertex] = color
                if backtrack(idx + 1):
                    return True
                del coloring[vertex]
        
        return False
    
    success = backtrack(0)
    return success, coloring if success else None

# Example: Some vertices already colored
graph = {
    'A': ['B', 'C', 'D'],
    'B': ['A', 'C'],
    'C': ['A', 'B', 'D'],
    'D': ['A', 'C']
}

precolored = {'A': 1, 'C': 2}  # A and C already colored
success, full_coloring = precoloring_extension(graph, precolored, 3)
print(f"Precoloring extension success: {success}")
print(f"Full coloring: {full_coloring}")

def is_bipartite(graph):
    """
    Check if graph is bipartite (2-colorable).
    Uses BFS to attempt 2-coloring.
    
    Args:
        graph: dict mapping vertices to lists of neighbors
    
    Returns:
        tuple: (is_bipartite, coloring or None)
    """
    from collections import deque
    
    coloring = {}
    
    for start_vertex in graph:
        if start_vertex in coloring:
            continue
        
        # BFS from this component
        queue = deque([start_vertex])
        coloring[start_vertex] = 1
        
        while queue:
            vertex = queue.popleft()
            current_color = coloring[vertex]
            next_color = 3 - current_color  # Toggle between 1 and 2
            
            for neighbor in graph[vertex]:
                if neighbor not in coloring:
                    coloring[neighbor] = next_color
                    queue.append(neighbor)
                elif coloring[neighbor] != next_color:
                    # Conflict: neighbor has wrong color
                    return False, None
        
    return True, coloring

# Example: Test bipartite graphs
bipartite_graph = {
    'A': ['B', 'D'],
    'B': ['A', 'C'],
    'C': ['B', 'D'],
    'D': ['A', 'C']
}

is_bip, coloring = is_bipartite(bipartite_graph)
print(f"Is bipartite: {is_bip}")  # True
print(f"2-coloring: {coloring}")

# Non-bipartite (triangle)
triangle = {
    'A': ['B', 'C'],
    'B': ['A', 'C'],
    'C': ['A', 'B']
}

is_bip, _ = is_bipartite(triangle)
print(f"Triangle is bipartite: {is_bip}")  # False

def find_chromatic_number_bounds(graph):
    """
    Find lower and upper bounds for chromatic number.
    
    Args:
        graph: dict mapping vertices to lists of neighbors
    
    Returns:
        tuple: (lower_bound, upper_bound)
    """
    # Lower bound: size of maximum clique
    # (Finding max clique is also NP-hard, so we approximate)
    max_degree = max(len(neighbors) for neighbors in graph.values())
    lower_bound = 2  # Minimum for non-empty graph with edges
    
    # Check for triangles (clique of size 3)
    for vertex in graph:
        neighbors = set(graph[vertex])
        for n1 in neighbors:
            for n2 in neighbors:
                if n1 != n2 and n2 in graph.get(n1, []):
                    lower_bound = max(lower_bound, 3)
    
    # Upper bound: max degree + 1 (Brooks' theorem)
    # For most graphs, χ(G) ≤ Δ(G) + 1
    upper_bound = max_degree + 1
    
    # Better upper bound: Welsh-Powell result
    coloring = welsh_powell_coloring(graph)
    upper_bound = min(upper_bound, max(coloring.values()))
    
    return lower_bound, upper_bound

# Example
graph = {
    'A': ['B', 'C', 'E'],
    'B': ['A', 'C', 'D'],
    'C': ['A', 'B', 'D', 'E'],
    'D': ['B', 'C', 'E'],
    'E': ['A', 'C', 'D']
}

lower, upper = find_chromatic_number_bounds(graph)
print(f"Chromatic number bounds: {lower} ≤ χ(G) ≤ {upper}")

def schedule_exams(students_courses):
    """
    Schedule exams using graph coloring.
    
    Args:
        students_courses: dict mapping students to list of courses
    
    Returns:
        dict: mapping courses to time slots
    """
    # Build conflict graph
    courses = set()
    for course_list in students_courses.values():
        courses.update(course_list)
    
    graph = {course: set() for course in courses}
    
    # Add edges for courses taken by same student
    for student, course_list in students_courses.items():
        for i, course1 in enumerate(course_list):
            for course2 in course_list[i+1:]:
                graph[course1].add(course2)
                graph[course2].add(course1)
    
    # Convert sets to lists for coloring algorithm
    graph = {k: list(v) for k, v in graph.items()}
    
    # Color the graph (colors = time slots)
    schedule = welsh_powell_coloring(graph)
    
    return schedule

# Example usage
students = {
    'Alice': ['Math', 'Physics', 'Chemistry'],
    'Bob': ['Math', 'Biology', 'English'],
    'Charlie': ['Physics', 'Biology', 'History'],
    'Diana': ['Chemistry', 'English', 'History']
}

exam_schedule = schedule_exams(students)
print("Exam Schedule:")
for course, time_slot in sorted(exam_schedule.items(), key=lambda x: x[1]):
    print(f"  Time slot {time_slot}: {course}")

num_slots = max(exam_schedule.values())
print(f"\nTotal time slots needed: {num_slots}")

def allocate_registers(live_ranges, num_registers):
    """
    Allocate registers to variables using graph coloring.
    
    Args:
        live_ranges: dict mapping variables to (start, end) tuples
        num_registers: number of available CPU registers
    
    Returns:
        dict: mapping variables to register numbers (or 'spill')
    """
    variables = list(live_ranges.keys())
    
    # Build interference graph
    graph = {var: [] for var in variables}
    for i, var1 in enumerate(variables):
        start1, end1 = live_ranges[var1]
        for var2 in variables[i+1:]:
            start2, end2 = live_ranges[var2]
            # Check if live ranges overlap
            if not (end1 < start2 or end2 < start1):
                graph[var1].append(var2)
                graph[var2].append(var1)
    
    # Try to color with available registers
    success, coloring = backtracking_coloring(graph, num_registers)
    
    if not success:
        # Need to spill some variables to memory
        coloring = greedy_coloring(graph)
        allocation = {}
        for var, color in coloring.items():
            if color <= num_registers:
                allocation[var] = f"R{color}"
            else:
                allocation[var] = "SPILL"
        return allocation
    
    # Map colors to register names
    return {var: f"R{color}" for var, color in coloring.items()}

# Example: Variable live ranges in a program
live_ranges = {
    'a': (1, 5),
    'b': (2, 7),
    'c': (3, 6),
    'd': (8, 10),
    'e': (4, 9)
}

allocation = allocate_registers(live_ranges, 3)
print("Register Allocation:")
for var, reg in sorted(allocation.items()):
    print(f"  Variable {var}: {reg}")

def assign_frequencies(towers, interference_distance):
    """
    Assign frequencies to radio towers.
    
    Args:
        towers: dict mapping tower IDs to (x, y) coordinates
        interference_distance: minimum distance to avoid interference
    
    Returns:
        dict: mapping tower IDs to frequency numbers
    """
    import math
    
    # Build interference graph
    graph = {tower: [] for tower in towers}
    
    tower_list = list(towers.keys())
    for i, tower1 in enumerate(tower_list):
        x1, y1 = towers[tower1]
        for tower2 in tower_list[i+1:]:
            x2, y2 = towers[tower2]
            distance = math.sqrt((x2-x1)**2 + (y2-y1)**2)
            if distance < interference_distance:
                graph[tower1].append(tower2)
                graph[tower2].append(tower1)
    
    # Assign frequencies (colors)
    frequencies = dsatur_coloring(graph)
    
    return frequencies

# Example: Tower locations
towers = {
    'T1': (0, 0),
    'T2': (5, 0),
    'T3': (10, 0),
    'T4': (0, 5),
    'T5': (5, 5),
    'T6': (10, 5)
}

freq_assignment = assign_frequencies(towers, interference_distance=7)
print("Frequency Assignment:")
for tower, freq in sorted(freq_assignment.items()):
    print(f"  {tower}: Frequency {freq}")
print(f"\nTotal frequencies needed: {max(freq_assignment.values())}")

def sudoku_to_graph():
    """
    Create graph representation of Sudoku constraints.
    
    Returns:
        dict: graph where vertices are cells, edges are constraints
    """
    graph = {}
    
    # Create vertices for all 81 cells
    for row in range(9):
        for col in range(9):
            cell = (row, col)
            graph[cell] = []
    
    # Add edges for row, column, and box constraints
    for row in range(9):
        for col in range(9):
            cell = (row, col)
            neighbors = set()
            
            # Same row
            for c in range(9):
                if c != col:
                    neighbors.add((row, c))
            
            # Same column
            for r in range(9):
                if r != row:
                    neighbors.add((r, col))
            
            # Same 3x3 box
            box_row, box_col = 3 * (row // 3), 3 * (col // 3)
            for r in range(box_row, box_row + 3):
                for c in range(box_col, box_col + 3):
                    if (r, c) != cell:
                        neighbors.add((r, c))
            
            graph[cell] = list(neighbors)
    
    return graph

def solve_sudoku(puzzle):
    """
    Solve Sudoku using graph coloring with constraints.
    
    Args:
        puzzle: 9x9 list with 0 for empty cells
    
    Returns:
        9x9 list with solution, or None if unsolvable
    """
    graph = sudoku_to_graph()
    coloring = {}
    
    # Pre-fill given numbers
    for row in range(9):
        for col in range(9):
            if puzzle[row][col] != 0:
                coloring[(row, col)] = puzzle[row][col]
    
    def is_safe(cell, digit):
        """Check if digit can be placed in cell."""
        for neighbor in graph[cell]:
            if coloring.get(neighbor) == digit:
                return False
        return True
    
    def solve():
        """Backtracking solver."""
        # Find next empty cell
        for row in range(9):
            for col in range(9):
                cell = (row, col)
                if cell not in coloring:
                    for digit in range(1, 10):
                        if is_safe(cell, digit):
                            coloring[cell] = digit
                            if solve():
                                return True
                            del coloring[cell]
                    return False
        return True
    
    if solve():
        # Convert back to 9x9 grid
        solution = [[0]*9 for _ in range(9)]
        for (row, col), digit in coloring.items():
            solution[row][col] = digit
        return solution
    return None

# Example Sudoku puzzle (0 = empty)
puzzle = [
    [5,3,0,0,7,0,0,0,0],
    [6,0,0,1,9,5,0,0,0],
    [0,9,8,0,0,0,0,6,0],
    [8,0,0,0,6,0,0,0,3],
    [4,0,0,8,0,3,0,0,1],
    [7,0,0,0,2,0,0,0,6],
    [0,6,0,0,0,0,2,8,0],
    [0,0,0,4,1,9,0,0,5],
    [0,0,0,0,8,0,0,7,9]
]

solution = solve_sudoku(puzzle)
if solution:
    print("Sudoku Solution:")
    for row in solution:
        print(row)

def color_map(regions_adjacency):
    """
    Color a map using graph coloring.
    
    Args:
        regions_adjacency: dict mapping regions to adjacent regions
    
    Returns:
        dict: mapping regions to colors
    """
    coloring = welsh_powell_coloring(regions_adjacency)
    return coloring

# Example: US states (simplified)
us_map = {
    'CA': ['OR', 'NV', 'AZ'],
    'OR': ['CA', 'NV', 'ID', 'WA'],
    'WA': ['OR', 'ID'],
    'NV': ['CA', 'OR', 'ID', 'UT', 'AZ'],
    'ID': ['OR', 'WA', 'NV', 'UT', 'WY', 'MT'],
    'AZ': ['CA', 'NV', 'UT', 'NM'],
    'UT': ['NV', 'ID', 'WY', 'CO', 'AZ', 'NM'],
    'MT': ['ID', 'WY', 'ND', 'SD'],
    'WY': ['ID', 'MT', 'UT', 'CO', 'NE', 'SD'],
    'CO': ['UT', 'WY', 'NE', 'KS', 'OK', 'NM', 'AZ'],
    'NM': ['AZ', 'UT', 'CO', 'OK', 'TX'],
    'ND': ['MT', 'SD', 'MN'],
    'SD': ['MT', 'WY', 'ND', 'NE', 'IA', 'MN'],
    'NE': ['WY', 'SD', 'CO', 'KS', 'MO', 'IA'],
    'KS': ['CO', 'NE', 'OK', 'MO'],
    'OK': ['CO', 'KS', 'NM', 'TX', 'AR', 'MO'],
    'TX': ['NM', 'OK', 'AR', 'LA'],
    'MN': ['ND', 'SD', 'IA', 'WI'],
    'IA': ['SD', 'NE', 'MN', 'MO', 'IL', 'WI'],
    'MO': ['NE', 'KS', 'IA', 'OK', 'AR', 'TN', 'KY', 'IL'],
    'AR': ['OK', 'TX', 'MO', 'LA', 'MS', 'TN'],
    'LA': ['TX', 'AR', 'MS'],
    'WI': ['MN', 'IA', 'IL', 'MI'],
    'IL': ['IA', 'MO', 'WI', 'IN', 'KY'],
    'MI': ['WI', 'IN', 'OH'],
    'IN': ['IL', 'MI', 'KY', 'OH'],
    'KY': ['MO', 'IL', 'IN', 'TN', 'VA', 'WV', 'OH'],
    'TN': ['MO', 'AR', 'KY', 'MS', 'AL', 'GA', 'NC', 'VA'],
    'MS': ['AR', 'LA', 'TN', 'AL'],
    'AL': ['MS', 'TN', 'FL', 'GA'],
    'OH': ['MI', 'IN', 'KY', 'PA', 'WV'],
    'WV': ['KY', 'OH', 'VA', 'PA', 'MD'],
    'VA': ['KY', 'TN', 'WV', 'NC', 'MD'],
    'NC': ['TN', 'VA', 'GA', 'SC'],
    'SC': ['NC', 'GA'],
    'GA': ['TN', 'AL', 'NC', 'SC', 'FL'],
    'FL': ['AL', 'GA'],
    'PA': ['OH', 'WV', 'NY', 'NJ', 'DE', 'MD'],
    'MD': ['WV', 'VA', 'PA', 'DE'],
    'DE': ['PA', 'MD', 'NJ'],
    'NJ': ['PA', 'DE', 'NY'],
    'NY': ['PA', 'NJ', 'VT', 'MA', 'CT']
}

map_coloring = color_map(us_map)
colors_used = max(map_coloring.values())
print(f"US Map colored with {colors_used} colors")
print("\nColor assignments:")
for state, color in sorted(map_coloring.items()):
    print(f"  {state}: Color {color}")

def greedy_coloring(graph, vertex_order=None):
    """
    Color graph using greedy algorithm.
    
    Args:
        graph: dict mapping vertices to lists of neighbors
        vertex_order: optional list specifying vertex order
    
    Returns:
        dict: mapping of vertices to colors
    """
    if vertex_order is None:
        vertex_order = list(graph.keys())
    
    coloring = {}
    
    for vertex in vertex_order:
        # Find colors used by neighbors
        neighbor_colors = set()
        for neighbor in graph[vertex]:
            if neighbor in coloring:
                neighbor_colors.add(coloring[neighbor])
        
        # Assign smallest available color
        color = 1
        while color in neighbor_colors:
            color += 1
        coloring[vertex] = color
    
    return coloring

# Example usage
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'C', 'D'],
    'C': ['A', 'B', 'D'],
    'D': ['B', 'C']
}

coloring = greedy_coloring(graph)
print(f"Greedy coloring: {coloring}")
print(f"Colors used: {max(coloring.values())}")

def welsh_powell_coloring(graph):
    """
    Color graph using Welsh-Powell algorithm.
    Orders vertices by degree (descending) before greedy coloring.
    
    Args:
        graph: dict mapping vertices to lists of neighbors
    
    Returns:
        dict: mapping of vertices to colors
    """
    # Sort vertices by degree (descending)
    vertices_by_degree = sorted(
        graph.keys(),
        key=lambda v: len(graph[v]),
        reverse=True
    )
    
    return greedy_coloring(graph, vertices_by_degree)

# Example
coloring_wp = welsh_powell_coloring(graph)
print(f"Welsh-Powell coloring: {coloring_wp}")
print(f"Colors used: {max(coloring_wp.values())}")

def backtracking_coloring(graph, max_colors):
    """
    Find optimal coloring using backtracking.
    
    Args:
        graph: dict mapping vertices to lists of neighbors
        max_colors: maximum number of colors to try
    
    Returns:
        tuple: (success, coloring dict)
    """
    vertices = list(graph.keys())
    coloring = {}
    
    def is_safe(vertex, color):
        """Check if color assignment is valid."""
        for neighbor in graph[vertex]:
            if coloring.get(neighbor) == color:
                return False
        return True
    
    def backtrack(vertex_idx):
        """Recursively try to color vertices."""
        if vertex_idx == len(vertices):
            return True
        
        vertex = vertices[vertex_idx]
        for color in range(1, max_colors + 1):
            if is_safe(vertex, color):
                coloring[vertex] = color
                if backtrack(vertex_idx + 1):
                    return True
                del coloring[vertex]
        
        return False
    
    success = backtrack(0)
    return success, coloring if success else {}

# Example
success, optimal_coloring = backtracking_coloring(graph, 3)
print(f"Backtracking success: {success}")
print(f"Optimal coloring: {optimal_coloring}")

def dsatur_coloring(graph):
    """
    Color graph using DSatur (Degree of Saturation) algorithm.
    Dynamically selects vertex with highest saturation degree.
    
    Args:
        graph: dict mapping vertices to lists of neighbors
    
    Returns:
        dict: mapping of vertices to colors
    """
    coloring = {}
    uncolored = set(graph.keys())
    
    def saturation_degree(vertex):
        """Count distinct colors used by neighbors."""
        neighbor_colors = set()
        for neighbor in graph[vertex]:
            if neighbor in coloring:
                neighbor_colors.add(coloring[neighbor])
        return len(neighbor_colors)
    
    def uncolored_degree(vertex):
        """Count uncolored neighbors."""
        return sum(1 for n in graph[vertex] if n in uncolored)
    
    # Color vertex with highest degree first
    first_vertex = max(graph.keys(), key=lambda v: len(graph[v]))
    coloring[first_vertex] = 1
    uncolored.remove(first_vertex)
    
    while uncolored:
        # Select vertex with highest saturation degree
        # Break ties with highest uncolored degree
        next_vertex = max(
            uncolored,
            key=lambda v: (saturation_degree(v), uncolored_degree(v))
        )
        
        # Find smallest available color
        neighbor_colors = {
            coloring[n] for n in graph[next_vertex] if n in coloring
        }
        color = 1
        while color in neighbor_colors:
            color += 1
        
        coloring[next_vertex] = color
        uncolored.remove(next_vertex)
    
    return coloring

# Example
coloring_dsatur = dsatur_coloring(graph)
print(f"DSatur coloring: {coloring_dsatur}")
print(f"Colors used: {max(coloring_dsatur.values())}")

def compare_algorithms(graph):
    """Compare different coloring algorithms."""
    algorithms = {
        'Greedy': greedy_coloring,
        'Welsh-Powell': welsh_powell_coloring,
        'DSatur': dsatur_coloring
    }
    
    print(f"Graph with {len(graph)} vertices")
    print("-" * 50)
    
    for name, algorithm in algorithms.items():
        coloring = algorithm(graph)
        colors_used = max(coloring.values())
        print(f"{name:15} Colors used: {colors_used}")
        print(f"                Coloring: {coloring}")
    
    # Try backtracking for small graphs
    if len(graph) <= 10:
        for k in range(1, len(graph) + 1):
            success, coloring = backtracking_coloring(graph, k)
            if success:
                print(f"{'Backtracking':15} Optimal colors: {k}")
                print(f"                Coloring: {coloring}")
                break

# Test on a more complex graph
complex_graph = {
    'A': ['B', 'C', 'E'],
    'B': ['A', 'C', 'D'],
    'C': ['A', 'B', 'D', 'E'],
    'D': ['B', 'C', 'E'],
    'E': ['A', 'C', 'D']
}

compare_algorithms(complex_graph)

# NetworkX - Graph library with coloring algorithms
import networkx as nx

G = nx.Graph()
G.add_edges_from([('A', 'B'), ('B', 'C'), ('C', 'A')])
coloring = nx.greedy_color(G, strategy='largest_first')
print(coloring)