Graph Coloring also called m coloring problem consists of coloring a given graph with at most m colors such that no adjacent vertices are assigned the same color Wikipedia: https:en.wikipedia.orgwikiGraphcoloring For each neighbour check if the coloring constraint is satisfied If any of the neighbours fail the constraint return False If all neighbours validate the constraint return True  neighbours  0,1,0,1,0  coloredvertices  0, 2, 1, 2, 0  color  1  validcoloringneighbours, coloredvertices, color True  color  2  validcoloringneighbours, coloredvertices, color False Does any neighbour not satisfy the constraints PseudoCode Base Case: 1. Check if coloring is complete 1.1 If complete return True meaning that we successfully colored the graph Recursive Step: 2. Iterates over each color: Check if the current coloring is valid: 2.1. Color given vertex 2.2. Do recursive call, check if this coloring leads to a solution 2.4. if current coloring leads to a solution return 2.5. Uncolor given vertex  graph  0, 1, 0, 0, 0, ...          1, 0, 1, 0, 1, ...          0, 1, 0, 1, 0, ...          0, 1, 1, 0, 0, ...          0, 1, 0, 0, 0  maxcolors  3  coloredvertices  0, 1, 0, 0, 0  index  3  utilcolorgraph, maxcolors, coloredvertices, index True  maxcolors  2  utilcolorgraph, maxcolors, coloredvertices, index False Base Case Recursive Step Color current vertex Validate coloring Backtrack Wrapper function to call subroutine called utilcolor which will either return True or False. If True is returned coloredvertices list is filled with correct colorings  graph  0, 1, 0, 0, 0, ...          1, 0, 1, 0, 1, ...          0, 1, 0, 1, 0, ...          0, 1, 1, 0, 0, ...          0, 1, 0, 0, 0  maxcolors  3  colorgraph, maxcolors 0, 1, 0, 2, 0  maxcolors  2  colorgraph, maxcolors
def valid_coloring(
    neighbours: list[int], colored_vertices: list[int], color: int
) -> bool:
    """
    For each neighbour check if the coloring constraint is satisfied
    If any of the neighbours fail the constraint return False
    If all neighbours validate the constraint return True

    >>> neighbours = [0,1,0,1,0]
    >>> colored_vertices = [0, 2, 1, 2, 0]

    >>> color = 1
    >>> valid_coloring(neighbours, colored_vertices, color)
    True

    >>> color = 2
    >>> valid_coloring(neighbours, colored_vertices, color)
    False
    """
    # Does any neighbour not satisfy the constraints
    return not any(
        neighbour == 1 and colored_vertices[i] == color
        for i, neighbour in enumerate(neighbours)
    )


def util_color(
    graph: list[list[int]], max_colors: int, colored_vertices: list[int], index: int
) -> bool:
    """
    Pseudo-Code

    Base Case:
    1. Check if coloring is complete
        1.1 If complete return True (meaning that we successfully colored the graph)

    Recursive Step:
    2. Iterates over each color:
        Check if the current coloring is valid:
            2.1. Color given vertex
            2.2. Do recursive call, check if this coloring leads to a solution
            2.4. if current coloring leads to a solution return
            2.5. Uncolor given vertex

    >>> graph = [[0, 1, 0, 0, 0],
    ...          [1, 0, 1, 0, 1],
    ...          [0, 1, 0, 1, 0],
    ...          [0, 1, 1, 0, 0],
    ...          [0, 1, 0, 0, 0]]
    >>> max_colors = 3
    >>> colored_vertices = [0, 1, 0, 0, 0]
    >>> index = 3

    >>> util_color(graph, max_colors, colored_vertices, index)
    True

    >>> max_colors = 2
    >>> util_color(graph, max_colors, colored_vertices, index)
    False
    """

    # Base Case
    if index == len(graph):
        return True

    # Recursive Step
    for i in range(max_colors):
        if valid_coloring(graph[index], colored_vertices, i):
            # Color current vertex
            colored_vertices[index] = i
            # Validate coloring
            if util_color(graph, max_colors, colored_vertices, index + 1):
                return True
            # Backtrack
            colored_vertices[index] = -1
    return False


def color(graph: list[list[int]], max_colors: int) -> list[int]:
    """
    Wrapper function to call subroutine called util_color
    which will either return True or False.
    If True is returned colored_vertices list is filled with correct colorings

    >>> graph = [[0, 1, 0, 0, 0],
    ...          [1, 0, 1, 0, 1],
    ...          [0, 1, 0, 1, 0],
    ...          [0, 1, 1, 0, 0],
    ...          [0, 1, 0, 0, 0]]

    >>> max_colors = 3
    >>> color(graph, max_colors)
    [0, 1, 0, 2, 0]

    >>> max_colors = 2
    >>> color(graph, max_colors)
    []
    """
    colored_vertices = [-1] * len(graph)

    if util_color(graph, max_colors, colored_vertices, 0):
        return colored_vertices

    return []
