Pattern Guide
Graph Coloring
"Assign colors so no adjacent vertices share a color. Greedy gives ≤ Δ+1 colors."
Graph coloring assigns colors to vertices so no adjacent pair shares a color. NP-hard in general (chromatic number), but: (1) bipartite graphs → 2-colorable (check with BFS); (2) greedy coloring → at most Δ+1 colors (Δ = max degree); (3) interval graphs → optimal greedy by endpoint; (4) planar graphs → 4-colorable (four color theorem). Useful for scheduling, register allocation, and map coloring.
Problems you can solve with this pattern
3 problems · click any to start solving
// Greedy coloring: at most Δ+1 colors
function greedyColoring(n, adjList) {
const colors = new Array(n).fill(-1);
for (let u = 0; u < n; u++) {
const used = new Set(adjList[u].map(v => colors[v]).filter(c => c >= 0));
let c = 0;
while (used.has(c)) c++;
colors[u] = c;
}
return { colors, numColors: Math.max(...colors) + 1 };
}
// Bipartite check (2-coloring)
function isBipartite(n, adjList) {
const color = new Array(n).fill(-1);
for (let start = 0; start < n; start++) {
if (color[start] !== -1) continue;
color[start] = 0;
const q = [start]; let i = 0;
while (i < q.length) {
const u = q[i++];
for (const v of adjList[u]) {
if (color[v] === -1) { color[v] = 1 - color[u]; q.push(v); }
else if (color[v] === color[u]) return false;
}
}
}
return true;
}
// Interval graph coloring (min colors = max overlapping intervals)
function intervalColoring(intervals) {
const events = intervals.flatMap(([s, e], i) => [[s, 0, i], [e, 1, i]]);
events.sort((a, b) => a[0] - b[0] || b[1] - a[1]); // ends before starts
const available = [], colors = new Array(intervals.length);
let maxColors = 0;
for (const [, type, i] of events) {
if (type === 0) { // start
const c = available.length ? available.pop() : maxColors++;
colors[i] = c;
} else { // end
available.push(colors[i]);
}
}
return { colors, numColors: maxColors };
}Greedy coloring: process vertices in some order, assign the smallest color not used by any neighbor. The result uses at most Δ+1 colors (Δ = maximum degree). For bipartite graphs: exactly 2 colors, detectable via BFS. For interval graphs (vertices = intervals, edges = overlapping intervals): sort by start time and color greedily — the chromatic number equals the maximum number of mutually overlapping intervals (=minimum rooms needed for meetings).
// Greedy coloring: at most Δ+1 colors
function greedyColoring(n, adjList) {
const colors = new Array(n).fill(-1);
for (let u = 0; u < n; u++) {
const used = new Set(adjList[u].map(v => colors[v]).filter(c => c >= 0));
let c = 0;
while (used.has(c)) c++;
colors[u] = c;
}
return { colors, numColors: Math.max(...colors) + 1 };
}
// Bipartite check (2-coloring)
function isBipartite(n, adjList) {
const color = new Array(n).fill(-1);
for (let start = 0; start < n; start++) {
if (color[start] !== -1) continue;
color[start] = 0;
const q = [start]; let i = 0;
while (i < q.length) {
const u = q[i++];
for (const v of adjList[u]) {
if (color[v] === -1) { color[v] = 1 - color[u]; q.push(v); }
else if (color[v] === color[u]) return false;
}
}
}
return true;
}
// Interval graph coloring (min colors = max overlapping intervals)
function intervalColoring(intervals) {
const events = intervals.flatMap(([s, e], i) => [[s, 0, i], [e, 1, i]]);
events.sort((a, b) => a[0] - b[0] || b[1] - a[1]); // ends before starts
const available = [], colors = new Array(intervals.length);
let maxColors = 0;
for (const [, type, i] of events) {
if (type === 0) { // start
const c = available.length ? available.pop() : maxColors++;
colors[i] = c;
} else { // end
available.push(colors[i]);
}
}
return { colors, numColors: maxColors };
}- General: NP-hard for chromatic number
- 2-coloring (bipartite): O(V+E) with BFS
- 3-coloring: NP-hard
- Greedy (any order): O(V+E), uses ≤ Δ+1 colors
- Interval graphs: optimal in O(n log n)
Special cases:
- Trees: always 2-colorable (bipartite)
- Planar graphs: 4-colorable (Four Color Theorem)
- Perfect graphs: chromatic number = clique number (polynomial)
Applications: Register allocation (variables conflict if lifetimes overlap), scheduling (conflicting tasks need different time slots), map coloring (adjacent regions different colors).