Chromatic Number: Algorithm Analysis and Code

Introduction and Core Concepts

The chromatic number of a graph, denoted as χ(G) (chi(G)), is one of the most fundamental and widely studied parameters in graph theory. Formally, the chromatic number is the smallest number of colors needed to color the vertices of a graph so that no two adjacent vertices share the same color. This type of coloring is called a proper vertex coloring, and the chromatic number represents the optimal solution to this coloring problem.

To understand why this concept is so central, consider a simple example. A graph with no edges requires only one color, so its chromatic number is 1. A complete graph K_n, where every vertex is connected to every other vertex, requires n colors because each vertex is adjacent to all others. A bipartite graph, such as a tree or an even cycle, has a chromatic number of 2. An odd cycle, like a triangle or a pentagon, requires 3 colors. These simple cases illustrate how the chromatic number captures the inherent complexity and density of a graph's structure.

Determining the chromatic number matters because it quantifies resource contention. Whenever a set of entities has pairwise conflicts, and conflicting entities cannot share the same resource, the problem naturally maps to graph coloring. The vertices represent entities, edges represent conflicts, colors represent resources (such as time slots, frequencies, or registers), and the chromatic number tells us the absolute minimum number of resources required to resolve all conflicts. This makes it a critical metric for optimization in scheduling, allocation, and partitioning problems.

It is important to distinguish the chromatic number from the act of finding a coloring. While many heuristic algorithms can produce a valid coloring using a small number of colors, proving that no coloring with fewer colors exists is computationally much harder. The decision problem "Is χ(G) ≤ k?" is NP-complete, and computing χ(G) exactly is NP-hard. This hardness is why the study of chromatic number involves both exact exponential algorithms and efficient approximation heuristics, each with different trade-offs in accuracy and performance.

How It Works

At its core, finding the chromatic number involves exploring the space of all possible vertex colorings. A proper k-coloring assigns each of the n vertices an integer from 0 to k-1 such that for every edge (u, v), the color of u is not equal to the color of v. The chromatic number is the smallest k for which such an assignment exists. The theoretical foundations for bounding and computing this number come from several key graph invariants.

Lower bounds tell us that we need at least a certain number of colors. The most important lower bound is the clique number, ω(G), which is the size of the largest complete subgraph. Since all vertices in a clique are mutually adjacent, they must all receive different colors, so χ(G) ≥ ω(G). Another powerful lower bound comes from the independence number, α(G), the size of the largest set of vertices with no edges between them. Since each color class forms an independent set, we need at least n / α(G) colors. For example, if a graph has 10 vertices and its largest independent set has size 3, at least 4 colors are needed.

Upper bounds tell us that a certain number of colors is always sufficient. A trivial upper bound is χ(G) ≤ n, as we can always give each vertex a unique color. A much tighter and more useful bound is given by Brooks' Theorem, which states that for any connected graph that is neither a complete graph nor an odd cycle, χ(G) ≤ Δ(G), where Δ(G) is the maximum degree of the graph. A simple constructive proof of the bound χ(G) ≤ Δ(G) + 1 is provided by the greedy coloring algorithm: if we color vertices one by one, each vertex has at most Δ neighbors already colored, so there is always an available color among Δ+1 choices.

The Search Strategy: From Bounds to Exact Value

Most exact algorithms for chromatic number work by systematically narrowing the gap between lower and upper bounds. They start with a lower bound L (e.g., clique number) and an upper bound U (e.g., from a greedy coloring). If L equals U, the chromatic number is found. Otherwise, the algorithm tests the feasibility of k-coloring for k between L and U, typically using backtracking with pruning. This is known as the decision-to-optimization reduction: we solve the optimization problem by solving a series of decision problems.

Backtracking explores a search tree where each level corresponds to assigning a color to a vertex. The key to efficiency is pruning: if a partial assignment already violates the coloring constraint, the entire subtree beneath it can be discarded. Advanced techniques order vertices intelligently (e.g., by degree or saturation), use forward checking to detect inevitable failures early, and employ branch-and-bound to cut off branches that cannot improve upon the best solution found so far. The interplay between tight bounds and aggressive pruning determines whether an exact algorithm can handle graphs with 50 vertices or 150 vertices in practice.

Implementation

Implementing chromatic number algorithms in Python requires a clear graph representation and careful handling of recursion and pruning. We will use an adjacency list for sparse graphs and an adjacency matrix for dense graphs, as both are common. The following implementations progress from a simple heuristic to an exact algorithm.

The first implementation is the classic greedy coloring algorithm, specifically the Welsh-Powell heuristic. It sorts vertices by descending degree and then assigns each vertex the smallest available color not used by its already-colored neighbors. While it does not guarantee the chromatic number, it provides a fast and often tight upper bound that is essential for seeding exact algorithms.

def greedy_welsh_powell(adj_list):
    """
    Greedy coloring using Welsh-Powell heuristic.
    Returns a coloring dict and number of colors used (upper bound).
    adj_list: dict {vertex: set(neighbors)}
    """
    # Sort vertices by degree descending - high degree first
    vertices = sorted(adj_list.keys(), key=lambda x: len(adj_list[x]), reverse=True)
    
    color = {}
    num_colors = 0
    
    for u in vertices:
        # Find colors used by neighbors
        neighbor_colors = set()
        for v in adj_list[u]:
            if v in color:
                neighbor_colors.add(color[v])
        
        # Assign smallest available color
        c = 0
        while c in neighbor_colors:
            c += 1
        
        color[u] = c
        if c + 1 > num_colors:
            num_colors = c + 1
            
    return color, num_colors

To compute the exact chromatic number, we need a backtracking algorithm that tests k-colorability. The core is the is_safe function, which checks if assigning a color to a vertex conflicts with its neighbors. The k-colorable function uses depth-first search to try all assignments. To find the chromatic number, we call this decision procedure iteratively for increasing k, starting from a lower bound.

def is_safe(vertex, c, color, adj_list):
    """Check if color c is safe for vertex given current assignment."""
    for neighbor in adj_list[vertex]:
        if color.get(neighbor) == c:
            return False
    return True

def k_colorable_util(vertex_idx, k, color, vertices, adj_list):
    """Recursive backtracking helper for k-colorability."""
    if vertex_idx == len(vertices):
        return True  # All vertices colored successfully
    
    v = vertices[vertex_idx]
    for c in range(k):
        if is_safe(v, c, color, adj_list):
            color[v] = c
            if k_colorable_util(vertex_idx + 1, k, color, vertices, adj_list):
                return True
            del color[v]  # Backtrack
    
    return False

def is_k_colorable(adj_list, k):
    """Decision problem: Can graph be colored with k colors?"""
    vertices = list(adj_list.keys())
    # Order by degree descending for better pruning
    vertices.sort(key=lambda x: len(adj_list[x]), reverse=True)
    return k_colorable_util(0, k, {}, vertices, adj_list)

def chromatic_number_exact(adj_list):
    """Find chromatic number via iterative deepening on k."""
    n = len(adj_list)
    # Lower bound: size of max clique (approximated by max degree + 1 is weak,
    # but we use greedy max clique heuristic for demo)
    # For simplicity, start from 1
    lower = 1
    # Upper bound from greedy
    _, upper = greedy_welsh_powell(adj_list)
    
    for k in range(lower, upper + 1):
        if is_k_colorable(adj_list, k):
            return k
    return upper

For larger graphs, the DSATUR (Degree of Saturation) algorithm is a significant improvement over simple greedy. DSATUR dynamically selects the next vertex to color as the one with the highest saturation degree — the number of different colors already used by its neighbors. This heuristic tends to color the most constrained vertices first, which dramatically reduces the search space and often finds the optimal or near-optimal coloring without exhaustive search.

def dsatur_coloring(adj_list):
    """
    DSATUR heuristic for graph coloring.
    Returns coloring and number of colors used.
    Often finds optimal chromatic number for many graphs.
    """
    n = len(adj_list)
    color = {}
    saturation = {v: set() for v in adj_list}
    uncolored = set(adj_list.keys())
    
    # Degree for tie-breaking
    degree = {v: len(adj_list[v]) for v in adj_list}
    
    while uncolored:
        # Select vertex with max saturation degree, tie-break by degree
        u = max(uncolored, key=lambda v: (len(saturation[v]), degree[v]))
        
        # Find smallest color not in saturation set
        used = saturation[u]
        c = 0
        while c in used:
            c += 1
        color[u] = c
        
        # Update saturation of uncolored neighbors
        for w in adj_list[u]:
            if w in uncolored:
                saturation[w].add(c)
        
        uncolored.remove(u)
    
    num_colors = max(color.values()) + 1 if color else 0
    return color, num_colors

An optimized exact algorithm combines branch-and-bound with bitmask representations for speed. By representing adjacency and color classes as integers (bitsets), we can perform conflict checks with fast bitwise operations. This is especially effective for graphs with up to 64 vertices, where a Python integer can hold the entire adjacency row.

def chromatic_number_branch_and_bound(adj_matrix):
    """
    Branch and bound with bitsets and pruning.
    adj_matrix: n x n boolean matrix
    Returns exact chromatic number.
    """
    n = len(adj_matrix)
    # Convert to bitmask adjacency
    adj_mask = [0] * n
    for i in range(n):
        mask = 0
        for j in range(n):
            if adj_matrix[i][j]:
                mask |= 1 << j
        adj_mask[i] = mask

    # Vertex ordering: descending degree
    order = sorted(range(n), key=lambda x: bin(adj_mask[x]).count('1'), reverse=True)
    # Reorder masks according to order
    reordered_mask = [0] * n
    for new_i, old_i in enumerate(order):
        m = 0
        for new_j, old_j in enumerate(order):
            if adj_matrix[old_i][old_j]:
                m |= 1 << new_j
        reordered_mask[new_i] = m

    best = n  # Upper bound
    colors = [-1] * n
    # color_masks[c] = bitmask of vertices with color c
    color_masks = [0] * n

    def bound(idx, used_colors):
        """Simple lower bound: used_colors + ceil(remaining / max_independent)"""
        # Prune if even optimistic bound cannot beat best
        if used_colors >= best:
            return True
        return False

    def dfs(idx, used_colors):
        nonlocal best
        if idx == n:
            if used_colors < best:
                best = used_colors
            return
        if bound(idx, used_colors):
            return
        
        # Try to assign existing colors
        for c in range(used_colors):
            # Check if vertex idx conflicts with color class c
            if (reordered_mask[idx] & color_masks[c]) == 0:
                colors[idx] = c
                color_masks[c] |= 1 << idx
                dfs(idx + 1, used_colors)
                color_masks[c] ^= 1 << idx
                colors[idx] = -1
        
        # Try a new color
        if used_colors + 1 < best:
            c = used_colors
            color_masks[c] |= 1 << idx
            colors[idx] = c
            dfs(idx + 1, used_colors + 1)
            color_masks[c] ^= 1 << idx
            colors[idx] = -1

    dfs(0, 0)
    return best

Step-by-Step Example

Let us walk through a concrete example to make the abstract concepts tangible. Consider the following graph G with 5 vertices {A, B, C, D, E} and edges: A-B, A-C, B-C, B-D, C-D, D-E. Visually, vertices A, B, C form a triangle, B, C, D form another triangle overlapping, and D connects to E as a pendant. What is the chromatic number of this graph?

First, we establish bounds. The subgraph induced by {A, B, C} is a complete graph K3, so the clique number ω(G) is at least 3. Therefore, χ(G) ≥ 3. The maximum degree Δ(G) is 3 (vertices B, C, D each have degree 3). By Brooks' Theorem, since the graph is not a complete graph K4 nor an odd cycle, we know χ(G) ≤ 3. Wait, careful: Brooks' Theorem says χ(G) ≤ Δ(G) for this graph, which would suggest χ(G) ≤ 3. Combined with χ(G) ≥ 3, this immediately tells us χ(G) = 3 without any search. This is a case where theoretical bounds are tight.

To see how an algorithm would discover this, let us simulate the DSATUR heuristic. Initially, saturation of all vertices is 0, so DSATUR picks the highest-degree vertex, say B (degree 3). It assigns B color 0. Next, it updates saturation: neighbors A, C, D now have saturation {0} (size 1), while E has saturation {} (size 0). Among {A, C, D}, all have saturation 1, so it tie-breaks by degree (all degree 2 or 3). Suppose it picks C next. C is adjacent to B (color 0), so it cannot use 0 and gets color 1. Now saturations are: A has {0,1} (neighbors B:0, C:1) size 2, D has {0,1} (neighbors B:0, C:1) size 2, E has {} size 0. DSATUR picks A next (saturation 2). A is adjacent to B:0 and C:1, so it needs a new color 2. D is adjacent to B:0 and C:1, so it also needs color 2, but wait D is adjacent to A? No, D is not adjacent to A, so D can reuse color 2? No, D is not adjacent to A, but D is adjacent to B and C, so colors 0 and 1 are forbidden, so D gets color 2 as well. Finally E is adjacent only to D (color 2), so E can reuse color 0. The final coloring uses colors {0,1,2} — 3 colors total.

Now consider the exact backtracking approach testing k=2. It would try to 2-color the graph. It assigns A=0, B=1 (since A-B edge), C must be different from both A and B, but with only 2 colors {0,1}, C is adjacent to A(0) and B(1), so no color is available — failure. The algorithm backtracks, tries A=0, B=1, but any assignment fails at C. It exhausts all possibilities for k=2 and concludes 2-coloring is impossible. It then tries k=3 and quickly finds the coloring described above: A=2, B=0, C=1, D=2, E=0, proving χ(G)=3. This walkthrough shows how lower bounds prune the search and how saturation guides the heuristic to the optimal solution efficiently.

Complexity Analysis

The computational complexity of chromatic number problems is a classic example of intractability. The decision problem "Is the graph k-colorable?" is NP-complete for any fixed k ≥ 3, and the optimization problem "What is χ(G)?" is NP-hard. This means no known polynomial-time algorithm exists for general graphs, and it is widely believed that none exists. All exact algorithms therefore have exponential worst-case time complexity.

For exact backtracking, the worst-case time is O(k^n) where n is the number of vertices, because in the worst case the search tree explores all k^n assignments. With iterative deepening from k=1 to χ(G), the total time is dominated by the final successful k=χ(G) call, so roughly O(χ(G)^n). Using inclusion-exclusion or the principle of counting independent sets, the best known exact algorithm runs in O(2.4423^n) time, and with exponential space, O(2^n) is achievable using the Lawler's algorithm based on dynamic programming over subsets. For practical branch-and-bound implementations, the runtime is highly instance-dependent — sparse graphs may be solved quickly, while dense, highly symmetric graphs can be extremely hard.

Heuristic algorithms trade optimality for speed. The greedy Welsh-Powell algorithm runs in O(n^2) or O(n + m) with adjacency lists (where m is number of edges) after sorting, which is O(n log n). DSATUR has a naive implementation of O(n^2) but can be implemented with a priority queue in O((n + m) log n). These heuristics provide an upper bound quickly but may overestimate the chromatic number. For example, there exist graphs where greedy uses n/2 colors while the chromatic number is 2 (e.g., a bipartite graph with a bad vertex ordering).

Space complexity is also an important consideration. Backtracking uses O(n + m) space for the graph plus O(n) recursion stack, so O(n + m) overall. Dynamic programming algorithms that store results for all subsets require O(2^n) space, which becomes infeasible beyond n=30-40. Bitmask branch-and-bound uses O(n) additional space for color masks, making it memory-efficient even for n=100, though time remains exponential.

Understanding these complexities helps in selecting the right tool. For n > 100, exact computation is usually infeasible, and heuristics or metaheuristics like simulated annealing, tabu search, or genetic algorithms are used to find good approximations. For n < 60, modern branch-and-bound solvers can often find the exact chromatic number within seconds or minutes.

Variations and Optimizations

The basic vertex coloring problem has several important variations, each with its own chromatic number variant and optimization techniques. Edge coloring, where colors are assigned to edges so that no two incident edges share a color, has its own chromatic index χ'(G). By Vizing's Theorem, χ'(G) is either Δ(G) or Δ(G)+1, making it much more constrained than vertex coloring. List coloring is another generalization where each vertex v has a list L(v) of permissible colors, and the list chromatic number χ_l(G) is the smallest k such that the graph is k-choosable. Fractional chromatic number χ_f(G) allows vertices to be assigned sets of colors, providing a linear programming relaxation that is often easier to compute and gives a strong lower bound.

For optimizing exact vertex coloring, several powerful techniques are used in state-of-the-art solvers. Vertex ordering is critical: ordering by degeneracy (smallest-last ordering) or by recursive largest first (RLF) can dramatically reduce the search tree. Forward checking and constraint propagation maintain for each uncolored vertex the set of colors still available; if any vertex runs out of available colors, the branch is pruned immediately. Another key optimization is using a maximal clique to obtain a strong initial lower bound — a large clique found via a heuristic like Bron-Kerbosch can often prove optimality without search.

Advanced Pruning and Memoization

Branch-and-bound can be enhanced with techniques borrowed from SAT solving. Color symmetries can be broken: if we have k colors, permuting the color labels yields the same solution, so we can enforce that the first occurrence of color c must appear before color c+1 to reduce redundant branches by a factor of k!. Memoization (caching) of failed subproblems using canonical representations of the remaining graph can avoid re-exploring isomorphic subtrees. Bit-parallelism, as shown in the code above, accelerates conflict checks from O(n) to O(1) word operations.

For very large graphs, incomplete methods are preferred. Tabu search maintains a current coloring (possibly improper) and moves by recoloring a vertex that participates in a conflict, using a tabu list to avoid cycling. Simulated annealing and genetic algorithms treat the number of conflicts as an energy function to minimize. Hybrid approaches often run a heuristic like DSATUR to get a good upper bound, then use a local search to try to reduce the number of colors by one, repeating until no improvement is found. These methods do not guarantee optimality but can handle graphs with thousands of vertices.

Preprocessing can also simplify the problem before search begins. Vertices of degree < k can be removed temporarily when testing k-colorability, because they can always be colored after the rest of the graph is colored (they have at most k-1 neighbors). This reduction, known as k-core decomposition, can shrink sparse graphs significantly. Similarly, if the graph is disconnected, its chromatic number is the maximum of the chromatic numbers of its connected components, allowing independent solving.

Real-World Applications

Although chromatic number originates in pure mathematics, its applications permeate computer science and operations research. The classic application is scheduling. In exam timetabling, each course is a vertex, an edge connects two courses if they share a student, and colors represent time slots. The chromatic number is the minimum number of time slots needed to schedule all exams without conflict. Universities use this model to minimize the exam period length while avoiding student overlaps. The same model applies to sports scheduling, conference session assignment, and university course timetabling.

In compiler design, register allocation is a direct application of graph coloring. Variables are vertices, an edge connects two variables whose live ranges overlap (they are needed at the same time), and colors correspond to physical CPU registers. If the graph's chromatic number is ≤ k (where k is the number of available registers), all variables can be kept in registers without spilling to memory. If χ(G) > k, some variables must be spilled, and the compiler uses coloring heuristics to decide which ones. This technique, pioneered by Chaitin, is used in GCC and LLVM.

Frequency assignment in wireless networks is another critical domain. Cell towers or radio stations are vertices, edges connect transmitters that would interfere if they used the same frequency, and colors are frequencies. The chromatic number gives the minimum spectrum needed to avoid interference. With the explosion of 5G and Wi-Fi networks, efficient coloring algorithms help maximize spectrum utilization. Similarly, in optical networks, wavelength assignment for lightpaths maps directly to edge coloring.

Beyond these, chromatic number appears in unexpected places. In Sudoku, the puzzle can be modeled as a graph with 81 vertices (cells) where edges connect cells in the same row, column, or 3x3 box; the graph has chromatic number 9, and a valid Sudoku solution is a 9-coloring. In social networks, coloring can be used for community detection and clustering. In web servers and databases, resource locking and deadlock avoidance can be modeled as coloring problems where transactions that conflict cannot be scheduled concurrently without proper isolation levels.

Comparison with Alternatives

When faced with a coloring problem, it is important to understand how the chromatic number relates to other graph parameters and algorithmic alternatives. Choosing the wrong invariant can lead to weak bounds or inefficient solutions. The table below compares the chromatic number with related concepts and the main algorithmic approaches for computing or approximating it.

The clique number ω(G) is the most common lower bound, but it can be arbitrarily far from χ(G). For example, Mycielski's construction produces triangle-free graphs (ω=2) with arbitrarily large chromatic number. The fractional chromatic number χ_f(G) is a linear programming relaxation that is always ≤ χ(G) and can be computed in polynomial time via the ellipsoid method, but it may be non-integer and still far from χ(G). The chromatic polynomial P(G, k) counts the number of proper k-colorings; evaluating it at k gives information about colorability but is #P-hard to compute.

Algorithmically, the choice is between exact methods that guarantee χ(G) and heuristics that are fast but approximate. Greedy algorithms are O(n log n) and simple to implement but highly dependent on vertex order — a bad ordering can use Δ+1 colors even when 2 suffice. DSATUR improves ordering dynamically and often finds the optimum but still has no guarantee. Backtracking with pruning guarantees optimality but is exponential. Modern exact solvers like DSATUR-based branch-and-bound or Zykov's recursion (which branches on whether two non-adjacent vertices get the same color or not) offer the best of both worlds for medium-sized graphs.

In practice, a robust chromatic number solver combines all these ideas: it computes a clique lower bound, runs greedy and DSATUR for an upper bound, and if the bounds do not match, launches a branch-and-bound search that uses both bounds for pruning. This hybrid strategy is far more effective than any single method alone.

Common Mistakes and Best Practices

Implementing and reasoning about chromatic number is error-prone, especially for developers new to graph algorithms. One of the most frequent mistakes is confusing the chromatic number with the number of colors used by a greedy algorithm. Greedy coloring provides an upper bound, not the chromatic number itself. For example, a bipartite graph (χ=2) can be colored with many more colors if vertices are processed in an adversarial order. Always remember: greedy ≤ Δ+1, but χ may be much smaller. To avoid this, never report greedy's result as the chromatic number without verification; use it only as an initial upper bound for exact search.

Another common pitfall is inefficient graph representation. Using an adjacency matrix for sparse graphs wastes O(n²) memory and makes neighbor iteration O(n) instead of O(degree). Conversely, using an adjacency list for dense graphs can make conflict checks slower. Choose the representation based on density: adjacency list (dict of sets) for sparse graphs (m << n²), bitsets or matrix for dense graphs. Also, failing to order vertices intelligently is a major performance killer for backtracking. Coloring vertices in arbitrary input order leads to exponentially larger search trees. Always sort by descending degree or use DSATUR ordering; this simple change can turn an intractable instance into a trivial one.

Recursion and pruning bugs are also prevalent. A typical error is forgetting to backtrack correctly — not removing a color assignment after a failed recursive call, which pollutes the state for subsequent branches. Another is incorrect pruning logic that cuts off the optimal solution. When implementing branch-and-bound, ensure the lower bound is truly a lower bound (never overestimates) and the upper bound is truly feasible. Off-by-one errors in color indices (0-based vs 1-based) can also cause subtle bugs where k-colorability is misjudged.

Best Practices for Robust Implementation

• Validate input: Check for self-loops (which make proper coloring impossible) and handle disconnected graphs by processing components separately.
• Use iterative deepening: Search for increasing k starting from a strong lower bound (max clique size) rather than trying to directly minimize colors in one search.
• Preprocess: Apply k-core reduction and remove low-degree vertices before search; they can be colored last without increasing the chromatic number.
• Profile and test: Test on known graphs: complete graphs (χ=n), bipartite graphs (χ=2), odd cycles (χ=3), and Mycielski graphs. Compare heuristic results against known optima.
• Escape and sanitize: When visualizing or exporting graphs, ensure proper HTML escaping for labels to prevent injection issues.
• Consider libraries: For production use, leverage optimized libraries like NetworkX, python-igraph, or OR-Tools which implement highly tuned coloring algorithms in C++.

Finally, be mindful of the exponential nature of the problem. Do not attempt exact computation on graphs with hundreds of vertices without heuristics or approximation. Set timeouts and fallback to heuristic solutions for large instances, and clearly document whether the returned value is exact or an upper bound.

Interview Questions

Chromatic number is a favorite topic in algorithm interviews because it tests understanding of NP-hardness, backtracking, and graph theory. Below are common questions and how to approach them.

Q1: What is the chromatic number of a tree, a bipartite graph, and a complete graph K_n?

Answer: A tree with at least one edge has chromatic number 2, because trees are bipartite and contain no odd cycles. More generally, any bipartite graph has χ=2 if it has at least one edge, and χ=1 if it has no edges. A complete graph K_n has χ=n because every vertex is adjacent to every other vertex, so each needs a distinct color. This question tests basic definitions. Mention that checking if χ ≤ 2 is polynomial (check bipartiteness via BFS), while χ ≤ 3 is NP-complete.

Q2: How would you determine if a graph is 2-colorable or 3-colorable? What is the complexity?

Answer: 2-colorability is equivalent to checking if the graph is bipartite, which can be done in O(n + m) using BFS/DFS two-coloring: start from any vertex, color it 0, color all neighbors 1, and so on; if you encounter an edge connecting same-colored vertices, the graph is not bipartite. 3-colorability is NP-complete, so no polynomial algorithm is known. You would use backtracking with pruning, trying all 3^n assignments in the worst case. In an interview, implement the BFS for 2-coloring and sketch the backtracking for 3-coloring, discussing pruning and ordering.

Q3: Explain why greedy coloring does not always give the chromatic number. Give an example.

Answer: Greedy coloring's result depends on vertex order. Consider a bipartite graph with vertices {a1,a2,b1,b2} where edges are a1-b1, a1-b2, a2-b1, a2-b2 (complete bipartite K2,2, χ=2). If ordered as a1, b1, a2, b2, greedy uses 2 colors optimally. But consider a path of 4 vertices ordered poorly, or more dramatically, the crown graph or a bipartite graph where ordering interleaves partitions badly can cause greedy to use many colors. A classic example: take a bipartite graph with partitions U={u1..n}, V={v1..n} and order vertices as u1, v1, u2, v2, ... Greedy will use 2 colors, but ordering as u1..un, v1..vn still uses 2. A better counterexample is the graph formed by taking a bipartite graph and ordering vertices such that each new vertex is adjacent to all previously used colors — this can force greedy to use Δ+1 colors while χ=2. Emphasize that greedy is an upper bound, not exact.

Q4: How would you find the chromatic number exactly for n ≤ 20?

Answer: For n ≤ 20, we can use exponential DP over subsets. Lawler's algorithm computes χ(G) in O(2.4423^n) by iterating over maximal independent sets. A simpler interview solution is iterative deepening with backtracking: for k from lower bound (clique size) to upper bound (greedy colors), test k-colorability via DFS with pruning. Mention bitmask optimization for speed and that 2^n = ~1M for n=20, which is feasible. Provide complexity analysis and discuss using memoization with bitmask DP: dp[mask] = true if subgraph induced by mask is k-colorable.

Q5: What is the relationship between chromatic number, clique number, and maximum degree?

Answer: For any graph G, ω(G) ≤ χ(G) ≤ Δ(G) + 1. The lower bound holds because a clique needs distinct colors. The upper bound holds via greedy coloring. Brooks' Theorem strengthens the upper bound to χ(G) ≤ Δ(G) unless G is a complete graph or odd cycle, where χ = Δ+1. Discuss that the gap between ω and χ can be arbitrarily large (Mycielski construction), so clique number is not always a tight lower bound. This question tests knowledge of bounds and their tightness.

Preparing for these questions involves not just memorizing definitions but being able to implement BFS bipartite check, sketch backtracking pseudocode, analyze complexity, and discuss trade-offs between exact and heuristic methods — all of which demonstrate deep algorithmic maturity.