Graph Coloring and Bipartite Check

Graph coloring assigns labels (colors) to vertices so that no two adjacent vertices share the same color. The most common question is bipartite checking — can you color the graph with exactly 2 colors? This comes up constantly in interviews disguised as “can you split nodes into two groups with no conflicts?”

What Is a Bipartite Graph?

A graph is bipartite if you can divide its vertices into two sets such that every edge goes between the sets — no edge connects two vertices in the same set. Equivalently, it’s 2-colorable.

Bipartite (2-colorable):          Not bipartite (odd cycle):
0(R) --- 1(B)                     0(R) --- 1(B)
|         |                        |         |
2(B) --- 3(R)                     2(R) --- 0(R)  ← conflict!
Set A = {0, 3} (Red)           Triangle has an odd cycle
Set B = {1, 2} (Blue)          — cannot 2-color

Key theorem: A graph is bipartite if and only if it contains no odd-length cycle.

Bipartite Check Using BFS

BFS level-by-level coloring is the cleanest approach:

from collections import deque

def is_bipartite_bfs(graph):
    n = len(graph)
    color = [-1] * n

    for start in range(n):
        if color[start] != -1:
            continue
        queue = deque([start])
        color[start] = 0

        while queue:
            node = queue.popleft()
            for neighbor in graph[node]:
                if color[neighbor] == -1:
                    color[neighbor] = 1 - color[node]
                    queue.append(neighbor)
                elif color[neighbor] == color[node]:
                    return False

    return True

graph = [[1, 3], [0, 2], [1, 3], [0, 2]]
print(is_bipartite_bfs(graph))  # True

graph_odd = [[1, 2], [0, 2], [0, 1]]
print(is_bipartite_bfs(graph_odd))  # False (triangle)

The outer loop handles disconnected components — each component is checked independently.

Bipartite Check Using DFS

The same logic works recursively:

def is_bipartite_dfs(graph):
    n = len(graph)
    color = [-1] * n

    def dfs(node, c):
        color[node] = c
        for neighbor in graph[node]:
            if color[neighbor] == -1:
                if not dfs(neighbor, 1 - c):
                    return False
            elif color[neighbor] == c:
                return False
        return True

    for i in range(n):
        if color[i] == -1:
            if not dfs(i, 0):
                return False
    return True

print(is_bipartite_dfs([[1, 3], [0, 2], [1, 3], [0, 2]]))  # True

Both BFS and DFS run in O(V + E).

M-Coloring Problem with Backtracking

Given a graph and m colors, can you color every vertex using at most m colors such that no two adjacent vertices share a color?

def can_color(graph, m):
    n = len(graph)
    colors = [0] * n

    def is_safe(node, c):
        for neighbor in graph[node]:
            if colors[neighbor] == c:
                return False
        return True

    def backtrack(node):
        if node == n:
            return True

        for c in range(1, m + 1):
            if is_safe(node, c):
                colors[node] = c
                if backtrack(node + 1):
                    return True
                colors[node] = 0

        return False

    if backtrack(0):
        return colors
    return None

graph = [[1, 2, 3], [0, 2], [0, 1, 3], [0, 2]]
print(can_color(graph, 3))  # [1, 2, 3, 2] (one valid coloring)
print(can_color(graph, 2))  # None (not 2-colorable)

This backtracking solution tries each color for each vertex and prunes branches where a conflict is found. Time complexity is O(m^V) in the worst case, but pruning makes it practical for small graphs.

LeetCode Problems

Is Graph Bipartite? (LeetCode 785)

Direct application of the BFS/DFS approach above. The graph is given as an adjacency list.

Possible Bipartition (LeetCode 886)

Given n people and a list of pairs who dislike each other, check if you can split everyone into two groups where no two people in the same group dislike each other. This is bipartite checking on the “dislike” graph.

def possible_bipartition(n, dislikes):
    graph = [[] for _ in range(n + 1)]
    for a, b in dislikes:
        graph[a].append(b)
        graph[b].append(a)

    color = [-1] * (n + 1)

    for i in range(1, n + 1):
        if color[i] != -1:
            continue
        queue = deque([i])
        color[i] = 0
        while queue:
            node = queue.popleft()
            for nei in graph[node]:
                if color[nei] == -1:
                    color[nei] = 1 - color[node]
                    queue.append(nei)
                elif color[nei] == color[node]:
                    return False
    return True

Real-World Applications

• Scheduling: assign time slots (colors) to tasks so conflicting tasks don’t overlap.
• Register allocation: compilers color an interference graph to assign CPU registers.
• Map coloring: color regions of a map so adjacent regions differ (the Four Color Theorem guarantees 4 suffice for planar graphs).
• Frequency assignment: assign radio frequencies to towers so nearby towers don’t interfere.

Complexity Summary

Interview Tips

• Bipartite check is O(V + E) — always mention this upfront.
• “Split into two groups” or “two-team assignment” problems are bipartite checks in disguise.
• The odd-cycle characterization is a useful proof tool — mention it when explaining correctness.
• For m-coloring, acknowledge it’s NP-hard in general but solvable with backtracking for small inputs.
• Union-Find can also solve bipartite checking — group each node with its neighbors’ complement. BFS is more intuitive for interviews.