Graph Coloring — Bipartite Check, Scheduling, and Constraints

Graph coloring sounds like a pure theory topic — and in general it is (k-coloring is NP-complete for k ≥ 3). But the special cases that show up in interviews are tractable and practical. Bipartite checking (2-coloring) is the most common. Interval scheduling and constraint problems are coloring in disguise. Knowing when a problem reduces to coloring gives you an immediate framework.

2-Coloring: Bipartite Check

A graph is bipartite if you can color every node with one of two colors such that no edge connects two nodes of the same color. Equivalently: no odd-length cycles.

This is the graph coloring problem you'll actually get in interviews. BFS or DFS, assigning alternating colors.

BFS Approach

from collections import deque

def is_bipartite(n, adj):
    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 adj[node]:
                if color[neighbor] == -1:
                    color[neighbor] = 1 - color[node]
                    queue.append(neighbor)
                elif color[neighbor] == color[node]:
                    return False

return True

JavaScript BFS

function isBipartite(n, adj) {
  const color = new Array(n).fill(-1);

for (let start = 0; start < n; start++) {
    if (color[start] !== -1) continue;
    const queue = [start];
    color[start] = 0;

while (queue.length > 0) {
      const node = queue.shift();
      for (const neighbor of adj[node]) {
        if (color[neighbor] === -1) {
          color[neighbor] = 1 - color[node];
          queue.push(neighbor);
        } else if (color[neighbor] === color[node]) {
          return false;
        }
      }
    }
  }

return true;
}

DFS Approach

def is_bipartite_dfs(n, adj):
    color = [-1] * n

def dfs(node, c):
        color[node] = c
        for neighbor in adj[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

function isBipartiteDFS(n, adj) {
  const color = new Array(n).fill(-1);

function dfs(node, c) {
    color[node] = c;
    for (const neighbor of adj[node]) {
      if (color[neighbor] === -1) {
        if (!dfs(neighbor, 1 - c)) return false;
      } else if (color[neighbor] === c) {
        return false;
      }
    }
    return true;
  }

for (let i = 0; i < n; i++) {
    if (color[i] === -1 && !dfs(i, 0)) return false;
  }
  return true;
}

The outer loop handles disconnected components. Without it, you'd miss isolated subgraphs that might not be bipartite.

O(V + E) time, O(V) space. Same as BFS/DFS traversal — coloring adds negligible overhead.

When to Check for Bipartiteness

• "Can you split nodes into two groups with no conflicts?"
• "Is the graph 2-colorable?"
• "Can students be divided into two teams such that no friends are on the same team?"
• Matching problems (bipartite matching requires a bipartite graph)
• "Does the graph contain an odd cycle?" (non-bipartite ↔ odd cycle)

Possible Bipartition (LeetCode 886)

"Can we split people into two groups such that no two people who dislike each other are in the same group?"

This is bipartite checking with extra words. Build a graph where dislikes are edges, check if it's bipartite.

def possible_bipartition(n, dislikes):
    adj = [[] for _ in range(n + 1)]
    for u, v in dislikes:
        adj[u].append(v)
        adj[v].append(u)

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

def dfs(node, c):
        color[node] = c
        for neighbor in adj[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(1, n + 1):
        if color[i] == -1:
            if not dfs(i, 0):
                return False
    return True

Interval Graph Coloring (Scheduling)

"Given a set of intervals (meetings), what's the minimum number of rooms needed?"

This is graph coloring on an interval graph. Two intervals conflict if they overlap. The minimum colors needed equals the chromatic number — which for interval graphs equals the maximum clique size (the most meetings happening simultaneously).

You don't need to actually build the graph. Sort events by time and sweep.

def min_rooms(intervals):
    events = []
    for start, end in intervals:
        events.append((start, 1))   # meeting starts
        events.append((end, -1))    # meeting ends

events.sort()

max_rooms = 0
    current = 0
    for _, delta in events:
        current += delta
        max_rooms = max(max_rooms, current)

return max_rooms

function minRooms(intervals) {
  const events = [];
  for (const [start, end] of intervals) {
    events.push([start, 1]);
    events.push([end, -1]);
  }

events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);

let maxRooms = 0, current = 0;
  for (const [, delta] of events) {
    current += delta;
    maxRooms = Math.max(maxRooms, current);
  }

return maxRooms;
}

O(n log n) for sorting. The sort tie-breaking matters: if a meeting ends and another starts at the same time, process the end first (that's what a[1] - b[1] achieves, since -1 < 1).

M-Coloring (Backtracking)

"Can you color a graph with at most M colors such that no adjacent nodes share a color?" For M ≥ 3, this is NP-complete. But for small graphs (interview-sized), backtracking works.

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

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

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

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

return False

return solve(0)

function canColor(adj, n, m) {
  const colors = new Array(n).fill(0);

function isSafe(node, color) {
    for (const neighbor of adj[node]) {
      if (colors[neighbor] === color) return false;
    }
    return true;
  }

function solve(node) {
    if (node === n) return true;

for (let color = 1; color <= m; color++) {
      if (isSafe(node, color)) {
        colors[node] = color;
        if (solve(node + 1)) return true;
        colors[node] = 0;
      }
    }

return false;
  }

return solve(0);
}

Exponential worst case (O(m^n)), but pruning makes it practical for small inputs. In interviews, this is about demonstrating backtracking skills, not efficiency.

Greedy Coloring

For approximate solutions on large graphs, greedy works: process nodes in some order, assign each node the smallest color not used by its neighbors.

def greedy_color(n, adj):
    colors = [-1] * n

for node in range(n):
        used = set()
        for neighbor in adj[node]:
            if colors[neighbor] != -1:
                used.add(colors[neighbor])

color = 0
        while color in used:
            color += 1
        colors[node] = color

return colors

function greedyColor(n, adj) {
  const colors = new Array(n).fill(-1);

for (let node = 0; node < n; node++) {
    const used = new Set();
    for (const neighbor of adj[node]) {
      if (colors[neighbor] !== -1) used.add(colors[neighbor]);
    }

let color = 0;
    while (used.has(color)) color++;
    colors[node] = color;
  }

return colors;
}

Greedy doesn't guarantee the minimum number of colors, but it uses at most Δ + 1 colors where Δ is the maximum degree. For many practical graphs, it's close to optimal.

Complexity Summary

Problem	Time	Space
Bipartite check (BFS/DFS)	O(V + E)	O(V)
Interval scheduling (sweep)	O(n log n)	O(n)
M-coloring (backtracking)	O(m^n) worst	O(n)
Greedy coloring	O(V + E)	O(V)

Common Mistakes

Not handling disconnected graphs. A graph can be bipartite overall but have disconnected components. You must check each component separately. Wrong tie-breaking in interval problems. If a meeting ends at time 5 and another starts at 5, do they conflict? Depends on the problem. Usually end < start means no conflict (half-open intervals). Sort end events before start events at the same time. Assuming greedy gives optimal coloring. It doesn't. Node ordering matters. For optimal coloring of general graphs, you need backtracking or specialized algorithms. Confusing "chromatic number" problems with "bipartite." Just because a problem involves coloring doesn't mean it's 2-coloring. Read carefully — if M > 2, it's a different (harder) problem.

Build intuition for graph coloring problems on CodeUp — start with bipartite checking, then move to scheduling problems to see how the same concept applies in different contexts.