Pattern Guide
Graph Coloring & Bipartite Checking
"Two-color graphs to find odd cycles. Divide into two groups satisfying constraints."
A graph is bipartite if and only if it has no odd-length cycles, equivalently if it's 2-colorable. BFS/DFS coloring: assign alternating colors. If a neighbor has the same color, graph is not bipartite. Applications: check if conflict graph is 2-colorable (exam scheduling, seating constraints), find maximum matching in bipartite graphs, detect odd cycles.
Problems you can solve with this pattern
3 problems · click any to start solving
function isBipartite(graph) {
const n = graph.length;
const color = new Array(n).fill(-1); // -1 = uncolored
for (let start = 0; start < n; start++) {
if (color[start] !== -1) continue; // already colored
const queue = [start];
color[start] = 0;
while (queue.length) {
const node = queue.shift();
for (const neighbor of graph[node]) {
if (color[neighbor] === -1) {
color[neighbor] = 1 - color[node]; // opposite color
queue.push(neighbor);
} else if (color[neighbor] === color[node]) {
return false; // same color = odd cycle = not bipartite
}
}
}
}
return true;
}Bipartite check: BFS from each unvisited node, color it 0. For each neighbor: if uncolored, color it 1-current; if same color as current, not bipartite. The two color sets form the two partitions. Possible vs impossible bipartite partition: equivalent to checking if constraint graph is 2-colorable. If any "must-be-different" pair ends up in same group, impossible.
function isBipartite(graph) {
const n = graph.length;
const color = new Array(n).fill(-1); // -1 = uncolored
for (let start = 0; start < n; start++) {
if (color[start] !== -1) continue; // already colored
const queue = [start];
color[start] = 0;
while (queue.length) {
const node = queue.shift();
for (const neighbor of graph[node]) {
if (color[neighbor] === -1) {
color[neighbor] = 1 - color[node]; // opposite color
queue.push(neighbor);
} else if (color[neighbor] === color[node]) {
return false; // same color = odd cycle = not bipartite
}
}
}
}
return true;
}Applications:
- Conflict graph partition: "must be in different groups" → edges in conflict graph → bipartite check
- Maximum bipartite matching: Hopcroft-Karp on bipartite graph
- Hungarian algorithm: min-cost bipartite matching
Odd cycle detection: If BFS finds same-color neighbor, the two paths from start to that neighbor form an odd cycle. The cycle length = dist[u] + dist[v] + 1.