M-Coloring Problem: Complete Implementation

1. Introduction and Core Concepts

The m-coloring problem is a classic decision and optimization problem in graph theory that asks whether the vertices of a given undirected graph can be colored using at most m colors such that no two adjacent vertices share the same color. Formally, given a graph G = (V, E) with n vertices and an integer m, we must assign a color from the set {1, 2, ..., m} to each vertex v ∈ V such that for every edge (u, v) ∈ E, color[u] ≠ color[v]. If such an assignment exists, the graph is said to be m-colorable.

This problem is a direct generalization of the famous map coloring problem and is deeply connected to the concept of the chromatic number. The chromatic number χ(G) of a graph is the smallest integer m for which the graph is m-colorable. Determining the chromatic number is equivalent to solving the m-coloring problem for successive values of m. For example, a graph that is 2-colorable is bipartite, while the Four Color Theorem states that every planar graph is 4-colorable. Understanding m-colorability therefore provides fundamental insight into the structure and constraints of a graph.

The m-coloring problem matters because it is NP-complete, making it a canonical example for studying backtracking, constraint satisfaction, and exponential-time algorithms. It has no known polynomial-time solution for general graphs when m ≥ 3, which means that for large graphs, we must rely on systematic search with intelligent pruning. For students and practitioners, it serves as an ideal vehicle for mastering backtracking because the state space is clear, the constraints are simple to check, and the pruning opportunities are intuitive. Beyond theory, the problem models a wide range of resource allocation and scheduling conflicts where adjacent entities cannot share the same resource.

Core Terminology

To work with the m-coloring problem effectively, you must understand its core components. The input is typically represented as an adjacency matrix or adjacency list, where graph[i][j] = 1 indicates an edge between vertex i and vertex j. The color assignment is stored in an array color[] of size n, where color[i] = 0 means uncolored and color[i] = k means vertex i has color k. A partial assignment is called promising if no two adjacent colored vertices share the same color, even if not all vertices are colored yet.

A closely related concept is the k-coloring vs. m-coloring distinction. While often used interchangeably, the decision problem (is the graph m-colorable?) differs from the optimization problem (find the minimum m). Backtracking solves the decision problem directly and can be wrapped in a loop to find the chromatic number. The search space for a naive approach is m^n possible assignments, which grows astronomically even for modest n and m. Backtracking aims to explore only a fraction of this space by abandoning partial assignments as soon as they violate the constraint.

2. How It Works

The m-coloring problem is solved using the backtracking paradigm, which is a depth-first, systematic search through the space of all possible color assignments. The algorithm builds a solution incrementally, one vertex at a time, and backtracks as soon as it detects that the current partial assignment cannot possibly be extended to a valid complete solution. This incremental construction can be visualized as a state-space tree where each level corresponds to a vertex and each branch corresponds to choosing one of the m colors for that vertex.

At the heart of the mechanism is the isSafe() function, also called the promising function. Before assigning color c to vertex v, the algorithm checks all neighbors of v that have already been colored. If any neighbor u has color[u] == c, then assigning c to v would create a conflict and the assignment is unsafe. Only safe colors are tried. If no safe color exists for vertex v, the algorithm has reached a dead end. It then backtracks to the previously colored vertex (v-1), erases its color, and tries the next available color for that vertex. This pruning is what distinguishes backtracking from brute-force enumeration.

The order in which vertices are colored significantly impacts performance. The simplest approach colors vertices in natural order 0, 1, 2, ..., n-1. More intelligent heuristics, such as ordering vertices by descending degree (largest degree first) or using the Minimum Remaining Values (MRV) heuristic, can dramatically reduce the search tree. A high-degree vertex has many constraints, so failing early on such a vertex prunes a larger subtree. This principle is central to optimizations like forward checking and constraint propagation.

The State-Space Tree

Consider a graph with n=4 and m=3. The root of the tree represents no vertices colored. Its three children represent assigning color 1, 2, or 3 to vertex 0. Each of those nodes has three children for vertex 1, and so on. A complete path from root to leaf at depth n represents a full assignment. The backtracking algorithm performs a depth-first traversal of this tree, but it cuts off entire subtrees whenever the isSafe check fails. For example, if vertices 0 and 1 are adjacent and both are assigned color 1, the node representing that assignment is a dead leaf and none of its descendants (which would assign colors to vertices 2 and 3) are ever explored.

This depth-first nature means the algorithm uses very little memory, only the current path from root to the current node, which is stored in the color array and the recursion stack. Unlike breadth-first search, it does not need to store the entire frontier. The algorithm terminates either when it finds a complete valid assignment (returning success for the decision problem) or when it has exhausted all possibilities and backtracked past the root, proving that no m-coloring exists.

3. Implementation

Implementing the m-coloring problem in Python requires a clear separation between the safety check, the recursive utility, and the driver function. The graph can be represented as either an adjacency matrix for dense graphs or an adjacency list for sparse graphs. The adjacency list is generally more efficient for the isSafe check because it iterates only over actual neighbors rather than all n vertices.

The first building block is the safety check. This function determines whether assigning a color to a vertex violates any constraints with already colored neighbors. It is called repeatedly, so its efficiency is critical.

def is_safe(v, graph, colors, c):
    """
    Check if color c can be assigned to vertex v.
    graph: adjacency matrix where graph[v][u] == 1 means edge
    colors: list where colors[i] is color of vertex i (0 = uncolored)
    c: color to test (1 to m)
    """
    n = len(graph)
    for u in range(n):
        # If there is an edge and neighbor has same color
        if graph[v][u] == 1 and colors[u] == c:
            return False
    return True

def is_safe_list(v, adj_list, colors, c):
    """Optimized version using adjacency list"""
    for neighbor in adj_list[v]:
        if colors[neighbor] == c:
            return False
    return True

The core recursive backtracking function attempts to color vertices sequentially. It takes the current vertex index v as a parameter. If v equals n, all vertices have been successfully colored. Otherwise, it iterates through all m colors, tries each safe color, recurses to the next vertex, and backtracks if the recursion fails. Note the careful handling of the base case and the backtrack step where colors[v] is reset to 0.

def m_coloring_util(graph, m, colors, v):
    """
    Recursive backtracking utility to solve m-coloring.
    Returns True if coloring possible from vertex v onwards.
    """
    n = len(graph)
    # Base case: all vertices are assigned a color
    if v == n:
        return True

    # Try different colors for vertex v (1 to m)
    for c in range(1, m + 1):
        if is_safe(v, graph, colors, c):
            colors[v] = c  # Assign color c to v

            # Recur to assign colors to rest of vertices
            if m_coloring_util(graph, m, colors, v + 1):
                return True

            # Backtrack: remove color assignment
            colors[v] = 0

    # No color could be assigned to v
    return False

def solve_m_coloring(graph, m):
    """Driver function to check if graph is m-colorable"""
    n = len(graph)
    colors = [0] * n
    if m_coloring_util(graph, m, colors, 0):
        return True, colors
    else:
        return False, None

For better performance on larger or sparser graphs, we can implement vertex ordering and an adjacency list representation. Ordering vertices by descending degree is a simple yet powerful heuristic that often reduces the search space by an order of magnitude. The following implementation also demonstrates how to find all possible colorings instead of just one.

def solve_m_coloring_ordered(adj_list, m):
    """
    Optimized solver using degree-based ordering.
    adj_list: adjacency list representation
    """
    n = len(adj_list)
    colors = [0] * n
    # Order vertices by degree descending (most constrained first)
    order = sorted(range(n), key=lambda x: len(adj_list[x]), reverse=True)
    # Map from ordered index to original vertex id
    # We will color in the order defined by 'order'

    def is_safe_ordered(pos, c):
        v = order[pos]
        for neighbor in adj_list[v]:
            if colors[neighbor] == c:
                return False
        return True

    def backtrack(pos):
        if pos == n:
            return True
        v = order[pos]
        for c in range(1, m + 1):
            if is_safe_ordered(pos, c):
                colors[v] = c
                if backtrack(pos + 1):
                    return True
                colors[v] = 0
        return False

    # Early pruning: if max degree >= m, may need more colors
    # But not sufficient to decide, just a quick check
    max_degree = max(len(neighbors) for neighbors in adj_list)
    if max_degree >= m and m < n:
        # Still need to search, this is not a definitive failure
        pass

    success = backtrack(0)
    return success, colors if success else None

Finally, many applications require enumerating all valid colorings or counting them, for example to find the number of distinct schedules. The following variant collects every solution by continuing the search after finding one, rather than terminating immediately.

def find_all_m_colorings(graph, m):
    """
    Find and count all valid m-colorings.
    Returns list of all color assignments.
    """
    n = len(graph)
    colors = [0] * n
    solutions = []

    def backtrack_all(v):
        if v == n:
            # Found a complete valid coloring, save a copy
            solutions.append(colors.copy())
            return
        for c in range(1, m + 1):
            if is_safe(v, graph, colors, c):
                colors[v] = c
                backtrack_all(v + 1)
                colors[v] = 0  # Backtrack

    backtrack_all(0)
    return solutions

# Example usage:
# graph = [[0,1,1,1],[1,0,1,0],[1,1,0,1],[1,0,1,0]]
# all_sols = find_all_m_colorings(graph, 3)
# print(f"Number of 3-colorings: {len(all_sols)}")
# for sol in all_sols:
#     print(sol)

4. Step-by-Step Example

Let us walk through a concrete example to illustrate exactly how backtracking prunes the search. Consider the following graph with 4 vertices: Vertex 0 is connected to 1, 2, and 3; Vertex 1 is connected to 0 and 2; Vertex 2 is connected to 0, 1, and 3; Vertex 3 is connected to 0 and 2. This graph is essentially a diamond shape with a diagonal. Its adjacency matrix is:

0: [0, 1, 1, 1]
1: [1, 0, 1, 0]
2: [1, 1, 0, 1]
3: [1, 0, 1, 0]

We will attempt to solve the 3-coloring problem (m=3) with colors {1, 2, 3}. We color vertices in order 0 → 1 → 2 → 3. The algorithm starts with colors = [0, 0, 0, 0] and v=0. It tries color 1 for vertex 0. isSafe(0, c=1) is true because no neighbors are colored yet. So it assigns colors[0]=1 and recurses to v=1.

For vertex 1, it tries color 1 first. isSafe(1, c=1) checks neighbor 0, which has color 1, so it returns False. The algorithm then tries color 2 for vertex 1. isSafe(1, c=2) is true (neighbor 0 is color 1). It assigns colors[1]=2 and recurses to v=2. Now colors = [1, 2, 0, 0]. For vertex 2, it tries color 1: neighbor 0 has color 1 → fails. Tries color 2: neighbor 1 has color 2 → fails. Tries color 3: neighbors are 0 (color 1) and 1 (color 2), so color 3 is safe. It assigns colors[2]=3 and recurses to v=3, with colors = [1, 2, 3, 0].

For vertex 3, neighbors are 0 (color 1) and 2 (color 3). Trying color 1 fails due to neighbor 0. Trying color 2 succeeds because neither neighbor has color 2. The algorithm assigns colors[3]=2, reaching v=4 which equals n, so it returns True. The final valid coloring is [1, 2, 3, 2]. This demonstrates a successful path without any backtracking.

Example Requiring Backtracking

To see backtracking, suppose the algorithm had made a different early choice that leads to a dead end. Imagine we try to 2-color the same graph (m=2), which is impossible because the graph contains a triangle (0-1-2). The trace would be: Assign 0→1, 1→2, then vertex 2 cannot be colored with 1 (conflict with 0) or 2 (conflict with 1), so it fails. The algorithm backtracks to vertex 1, resets colors[1]=0, tries the next color for vertex 1 (but m=2, so no more colors), returns False to vertex 0. Vertex 0 then tries color 2, and the same failure repeats for the other branch. After exhausting both colors for vertex 0, the algorithm concludes the graph is not 2-colorable. This exhaustive failure and systematic backtrack is the essence of proving non-colorability.

This step-by-step process highlights why the isSafe check must only consider already colored vertices. If we checked uncolored vertices (color 0), we would incorrectly prune valid branches. The algorithm's correctness depends on exploring the state-space tree depth-first and only pruning when a constraint is definitively violated.

5. Complexity Analysis

Analyzing the complexity of the m-coloring problem requires distinguishing between the complexity of the problem itself and the complexity of the backtracking algorithm that solves it. The decision problem is NP-complete, meaning no known polynomial-time algorithm exists for general graphs. The backtracking algorithm has an exponential worst-case time complexity, but its actual runtime varies dramatically based on the graph structure, the value of m, and the vertex ordering.

In the worst case, the algorithm explores the entire state-space tree. At each of the n levels, it branches m ways, leading to O(m^n) leaves. For each node, it performs an isSafe check that scans up to n neighbors (or degree(v) with an adjacency list). Therefore, the worst-case time complexity is O(m^n * n) with an adjacency matrix, or O(m^n * d) where d is the average degree with an adjacency list. This worst case occurs when the graph is not m-colorable or when it is barely m-colorable and the solution is in the last branch explored, forcing the algorithm to examine almost all possibilities. For example, a complete graph K_n with m = n-1 will force exhaustive search.

The best case is much faster. If the graph is easily colorable and the first color tried at each vertex leads to a solution, the algorithm finds a solution after exploring only one path of depth n, performing n isSafe checks. This yields O(n * d) time, which is linear in the graph size. This occurs, for instance, when m is much larger than the chromatic number or when the graph is sparse and the vertex ordering is favorable. The average case lies between these extremes and is difficult to characterize theoretically, as it depends heavily on the random graph model and the ratio of m to the graph's density.

Space complexity is a major advantage of backtracking. The algorithm only needs to store the graph representation, the color array of size n, and the recursion stack of depth at most n. Thus the auxiliary space is O(n) besides the input graph storage, which is O(n^2) for an adjacency matrix or O(n + e) for an adjacency list where e is the number of edges. This is exponentially more space-efficient than breadth-first search or dynamic programming approaches that might store all partial assignments.

It is important to note that while O(m^n) looks identical to brute force, backtracking is often far faster in practice due to pruning. For sparse graphs, many branches are cut early. For dense graphs, conflicts are detected quickly. The table above reflects this nuance: the best case for finding one solution is linear, while proving non-colorability always requires exhaustive search in the worst case.

6. Variations and Optimizations

The naive backtracking algorithm can be significantly improved with several well-known optimizations that reduce the effective search space without changing the worst-case asymptotic complexity. These techniques are essential for handling graphs with more than 20-30 vertices.

The most effective optimization is intelligent vertex ordering. The static ordering heuristic sorts vertices by descending degree before starting the search, ensuring the most constrained vertices are colored first. An even stronger dynamic heuristic is the Minimum Remaining Values (MRV) or smallest domain first: at each step, choose the uncolored vertex that has the fewest legal colors remaining given the current partial assignment. Another powerful heuristic is the Brelaz heuristic (DSATUR), which selects the vertex with the highest saturation degree — the number of different colors already used by its neighbors. These orderings cause failures to be discovered higher in the tree, pruning larger subtrees.

Forward checking is a constraint propagation technique that goes beyond the simple isSafe check. When a color is assigned to vertex v, forward checking removes that color from the domains of all uncolored neighbors of v. If any neighbor's domain becomes empty, the algorithm backtracks immediately without recursing deeper. This look-ahead prevents the algorithm from exploring branches that are doomed to fail one level deeper. More advanced propagation like Maintaining Arc Consistency (MAC) can further prune by enforcing consistency across the entire graph, though with higher overhead per node.

Other variations include branch and bound for the optimization version (finding the chromatic number) where an upper bound on χ(G) is maintained and branches that cannot improve the bound are pruned. For counting all colorings, symmetry breaking can be used: since permuting color labels yields an equivalent coloring, we can fix the color of the first vertex to 1 to reduce the search space by a factor of m. Bitmask representations can also accelerate the isSafe check by representing color domains as bitsets and using bitwise operations, which is especially fast in languages like Python with integer bit operations or in C++.

Common Variants of the Problem

The m-coloring problem has several important variants. The List Coloring variant gives each vertex v a specific list L(v) of allowed colors, rather than the same set {1..m} for all vertices. The Precoloring Extension variant has some vertices already colored and asks if the coloring can be extended. The Equitable Coloring variant requires that color classes differ in size by at most one, adding a global cardinality constraint. Each variant requires slight modifications to the isSafe function and the domain initialization but retains the same backtracking skeleton.

7. Real-World Applications

Although the m-coloring problem is abstract, its structure appears surprisingly often in practical systems where conflicts must be avoided and resources must be reused. Any situation where entities that interact or overlap cannot share the same resource can be modeled as a graph coloring problem.

In compiler design, register allocation is a direct application. Variables that are live at the same time interfere and cannot be assigned to the same CPU register. The compiler builds an interference graph where vertices are variables and edges connect interfering variables. Coloring this graph with m colors, where m is the number of available registers, determines a valid register assignment. If the graph is not m-colorable, some variables must be spilled to memory. Modern compilers like LLVM and GCC use sophisticated graph coloring heuristics derived from backtracking and greedy algorithms for this critical optimization.

Scheduling and timetabling problems are another major domain. In university exam scheduling, each course is a vertex and an edge connects two courses if they share a student. Colors represent time slots. An m-coloring corresponds to a conflict-free exam schedule using m time slots. Similarly, in operating systems, job scheduling where jobs that require the same resource cannot run simultaneously is a coloring problem. Even sports tournament scheduling, where teams that have already played each other should not be scheduled in the same round, maps to graph coloring.

Frequency assignment in wireless networks is a classic engineering application. Cell towers or radio stations that are geographically close and would interfere if they broadcast on the same frequency are represented as adjacent vertices. Colors represent frequencies. The goal is to assign frequencies using the minimum spectrum (minimum m) while avoiding interference. This is crucial for cellular networks, Wi-Fi channel allocation, and radio astronomy. The same model applies to traffic light phasing, where incompatible traffic movements cannot have a green light simultaneously.

Sudoku is a well-known puzzle that is exactly a 9-coloring problem on a graph with 81 vertices, where edges connect cells in the same row, column, or 3x3 box. Solving Sudoku via backtracking is therefore a direct instance of the m-coloring algorithm with m=9 and additional constraints. This connection makes the m-coloring problem a popular teaching tool for constraint satisfaction.

8. Comparison with Alternatives

Backtracking is not the only approach to graph coloring. Depending on whether you need an exact solution, an approximate solution, or a solution for a specific graph class, other algorithms may be more appropriate. Understanding the trade-offs is crucial for choosing the right tool.

Brute Force enumeration generates all m^n assignments and checks each one for validity. While conceptually simple, it never prunes and always pays the full O(m^n * n) cost, even when a conflict is obvious after coloring just two adjacent vertices. Backtracking is strictly superior because it prunes invalid partial assignments early, often exploring orders of magnitude fewer nodes.

Greedy coloring algorithms, such as Welsh-Powell (order by descending degree and assign the smallest available color), are extremely fast at O(n^2) or O(n log n + e) but do not guarantee an optimal or even correct decision for a fixed m. They produce a coloring using at most Δ+1 colors (where Δ is maximum degree) but may use more colors than necessary and cannot prove that a graph is not m-colorable. They are useful for obtaining an upper bound on the chromatic number quickly, which can then be used to prune a backtracking search.

More advanced exact methods include DSATUR (Degree of Saturation), which is a branch-and-bound algorithm that combines backtracking with the saturation heuristic, and Lawler's dynamic programming algorithm which runs in O(2.44^n) time but uses exponential space. For large graphs where exact solutions are infeasible, metaheuristics like Simulated Annealing, Tabu Search, and Genetic Algorithms can find good approximate colorings without guaranteeing optimality.

In practice, a hybrid approach often works best: use a greedy algorithm to get a quick upper bound U, then run backtracking or DSATUR to try to find a coloring with m = U-1, U-2, etc., to find the true chromatic number. This combination leverages the speed of greedy methods and the exactness of backtracking.

9. Common Mistakes and Best Practices

Implementing the m-coloring problem correctly requires attention to several subtle pitfalls that can lead to incorrect results, infinite recursion, or severe performance degradation. Awareness of these common mistakes is essential for both interviews and production code.

A frequent mistake is an incorrect isSafe implementation that checks uncolored vertices or uses the wrong adjacency representation. Remember that colors[v] = 0 means uncolored, so the check colors[u] == c should only fail when the neighbor is actually colored with c. Some beginners mistakenly check graph[v][u] == 1 and colors[u] != 0 and colors[u] == c which is redundant but harmless, or worse, they forget to handle the adjacency matrix symmetry and only check one direction. Always ensure you iterate over all neighbors and compare against the candidate color c, not against colors[v].

Another critical error is failing to backtrack correctly. After a recursive call returns False, you must reset colors[v] = 0 before trying the next color. Forgetting this reset leaves a stale color that pollutes subsequent isSafe checks for sibling branches, causing the algorithm to incorrectly report failure. Similarly, some implementations incorrectly return False immediately after the first failed color, rather than continuing the loop to try all m colors. The loop for c in range(1, m+1) must exhaust all options before declaring failure for vertex v.

Off-by-one errors with color indices are also common. If you use colors 0 to m-1 instead of 1 to m, ensure your isSafe and initialization are consistent. Using 0 as both a valid color and the uncolored sentinel is a classic bug. Best practice is to use 0 for uncolored and 1..m for actual colors, as shown in the implementations above. Additionally, not handling the base case if v == n: return True correctly can cause index out-of-bounds errors or missed solutions.

Best Practices

To write robust and efficient code, follow these best practices. First, choose the right graph representation: use an adjacency list for sparse graphs (e << n^2) to make isSafe O(degree) instead of O(n). Second, implement vertex ordering. Even a simple static sort by descending degree can cut runtime by 50% or more on many graphs. Third, add simple early checks: if m > n, the answer is trivially True; if the graph contains a clique of size > m, the answer is trivially False (since a clique of size k needs k colors). Checking for large cliques quickly can avoid exponential search entirely.

For recursion depth, Python's default recursion limit (~1000) may be exceeded for large graphs. Consider implementing an iterative backtracking version using an explicit stack, or increase the recursion limit with sys.setrecursionlimit(). Always test your implementation on known cases: an empty graph (should be 1-colorable), a complete graph K_n (needs n colors), a bipartite graph (needs 2 colors), and an odd cycle (needs 3 colors). Finally, for interview settings, clearly explain the state-space tree and the pruning condition before diving into code, as interviewers value conceptual clarity over syntactic perfection.

10. Interview Questions

Mastering the m-coloring problem is a strong signal of your understanding of backtracking and NP-completeness. Interviewers often use it to probe your ability to design recursive algorithms, analyze exponential complexity, and apply heuristics. Below are common questions and how to approach them.

Q1: How do you determine if a graph is m-colorable? Explain the backtracking approach.

Answer: Use a recursive backtracking algorithm that tries to assign colors vertex by vertex. Define a helper function isSafe(v, c) that checks if any already-colored neighbor of v has color c. The recursive function solve(v) tries each color c from 1 to m for vertex v; if isSafe, it assigns c and recurses to v+1. If recursion succeeds, return True; otherwise backtrack by resetting the color and trying the next c. If no color works for v, return False. The base case is v == n, meaning all vertices are colored successfully. Emphasize the pruning: we abandon a branch as soon as a conflict is detected, avoiding exploration of its entire subtree. Mention time O(m^n) worst case and space O(n).

Q2: What is the difference between the m-coloring problem and finding the chromatic number? How would you find the chromatic number using your m-coloring solver?

Answer: The m-coloring problem is a decision problem: given m, is the graph m-colorable? The chromatic number χ(G) is the optimization problem: what is the smallest such m? To find χ(G), you can iteratively call the m-coloring solver for m = 1, 2, 3, ... until it returns True. The first m that succeeds is the chromatic number. Optimization: you can binary search on m between 1 and n, or start from a lower bound (size of maximum clique) and an upper bound (from a greedy coloring, at most Δ+1) to reduce the number of calls. Note that this still requires solving an NP-complete problem multiple times, so the overall complexity remains exponential.

Q3: How would you optimize the naive backtracking solution for m-coloring?

Answer: Discuss three levels of optimization. First, vertex ordering: color high-degree vertices first (static ordering) or dynamically choose the vertex with fewest remaining legal colors (MRV) or highest saturation (DSATUR). Second, forward checking: maintain domains for uncolored vertices and prune a color from neighbors' domains when assigned; backtrack immediately if any domain becomes empty. Third, early pruning checks: if m == 1, check if graph has no edges; if graph contains a (m+1)-clique, immediately return False. Also mention using an adjacency list and bitmask representations for faster isSafe checks. Explain that these do not improve worst-case O(m^n) but dramatically improve average-case performance.

Q4: What is the time and space complexity of your solution? Can it be solved in polynomial time?

Answer: Worst-case time is O(m^n * n) because in the worst case we explore all m^n assignments and each isSafe check scans up to n neighbors. Best case is O(n*d) when the first path succeeds. Space is O(n) for the color array and recursion stack plus O(n^2) or O(n+e) for the graph. Then explain NP-completeness: for general graphs and m ≥ 3, no polynomial-time algorithm is known, and it is NP-complete (reducible from 3-SAT). However, special cases are polynomial: m=2 is bipartite checking via BFS/DFS in O(n+e), and for certain graph classes like trees, interval graphs, or planar graphs with m=4, polynomial algorithms exist.

Q5: How would you modify your algorithm to count the number of valid m-colorings or to list all of them?

Answer: Instead of returning True immediately when v == n, increment a counter or append a copy of the colors array to a results list, then return to continue searching. The backtracking structure remains the same, but you do not terminate early; you explore the entire search tree, backtracking after each solution to find the next one. The time becomes O(m^n * n) in all cases because you must enumerate all leaves. Mention symmetry breaking to avoid counting color permutations as distinct if needed, and that the number of solutions can be exponential, so storing them all may require exponential space.