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 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 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 recursive step color current vertex validate coloring backtrack 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
def valid_coloring(
    neighbours: list[int], colored_vertices: list[int], color: int
) -> bool:
    
    
    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:
    

    
    if index == len(graph):
        return True

    
    for i in range(max_colors):
        if valid_coloring(graph[index], colored_vertices, i):
            
            colored_vertices[index] = i
            
            if util_color(graph, max_colors, colored_vertices, index + 1):
                return True
            
            colored_vertices[index] = -1
    return False


def color(graph: list[list[int]], max_colors: int) -> list[int]:
    
    colored_vertices = [-1] * len(graph)

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

    return []