Colors a graph so that no two adjacent vertices share the same color using a backtracking approach.

# Graph Coloring - Backtracking
# Description: Colors a graph so that no two adjacent vertices share the same color using a backtracking approach.

def graph_coloring(graph, num_colors):
    """
    Color a graph using backtracking to ensure no adjacent nodes share a color.

    This algorithm attempts to assign colors to graph nodes such that no 
    two adjacent nodes have the same color, using the minimum number of colors possible.

    Args:
        graph (dict): Adjacency list representing graph connections.
        num_colors (int): Maximum number of colors available for coloring.

    Returns:
        dict: Mapping of nodes to colors, or None if no valid coloring exists.

    Time Complexity: O(num_colors^V), where V is the number of vertices
    Space Complexity: O(V)

    Note: This is an NP-hard problem, so the algorithm uses backtracking.
    """
    # Initialize coloring with uncolored nodes
    coloring = {node: -1 for node in graph}
    nodes = list(graph.keys())

    def is_color_valid(node, color):
        """
        Check if a color can be assigned to a node without conflicts.

        Args:
            node (int): Current node being colored
            color (int): Color being considered

        Returns:
            bool: True if color can be assigned, False otherwise
        """
        # Check all adjacent nodes to ensure no color conflicts
        for neighbor in graph[node]:
            # Skip uncolored neighbors
            if coloring[neighbor] == -1:
                continue
            # Check for color conflict with colored neighbors
            if coloring[neighbor] == color:
                return False
        return True

    def backtrack_color(node_index):
        """
        Recursive backtracking function to color the graph.

        Args:
            node_index (int): Index of the current node being processed

        Returns:
            bool: True if a valid coloring is found, False otherwise
        """
        # Base case: all nodes have been colored successfully
        if node_index == len(nodes):
            return True

        # Get the current node to color
        current_node = nodes[node_index]

        # Try coloring the current node with each available color
        for color in range(num_colors):
            # Check if the current color is valid for this node
            if is_color_valid(current_node, color):
                # Assign the color
                coloring[current_node] = color

                # Recursively try to color the next node
                if backtrack_color(node_index + 1):
                    return True

                # Backtrack: reset the color if solution not found
                coloring[current_node] = -1

        # No valid coloring found
        return False

    # Attempt to color the graph
    return coloring if backtrack_color(0) else None