Graph Coloring and Bipartite Check
DSA · Graphs
Theory
Graph coloring assigns a color to each vertex so that no two connected vertices share a color. The minimum number of colors needed is called the chromatic number. Checking whether a graph can be colored with just two colors is the same as asking whether it is bipartite: whether its vertices can be split into two groups with every edge going between the groups. This two-color check is easy: run BFS or DFS, give the start node color 0, give every neighbour the opposite color, and fail if you ever find an edge connecting two nodes of the same color. A graph is bipartite exactly when it has no odd-length cycle. Coloring with three or more colors is NP-hard in general, so greedy heuristics are used in practice.
Why we use it
Coloring models scheduling and assignment problems where conflicts must be kept apart: exam timetables, register allocation in compilers, frequency assignment for mobile towers, and matching problems.
When to use it
Use the bipartite check for "split into two teams with no conflict" problems. Use greedy coloring when you need a good, not necessarily optimal, schedule with many colors.
How it works
- Color start node 0
- BFS: for each neighbour
- Neighbour uncolored? Yes: Give it the opposite color. No: Compare colors.
- Same color as current node? Yes: Not bipartite. No: Continue.
- All edges checked: bipartite
Syntax
Bipartite check (BFS) O(V + E)
Greedy coloring O(V + E)
Optimal k-coloring NP-hardExample
from collections import deque
def is_bipartite(graph):
color = {}
for start in graph:
if start in color:
continue
color[start] = 0
q = deque([start])
while q:
u = q.popleft()
for v in graph[u]:
if v not in color:
color[v] = 1 - color[u]
q.append(v)
elif color[v] == color[u]:
return False, color
return True, color
square = {"A": ["B", "D"], "B": ["A", "C"], "C": ["B", "D"], "D": ["A", "C"]}
triangle = {"A": ["B", "C"], "B": ["A", "C"], "C": ["A", "B"]}
print("Square:", is_bipartite(square))
print("Triangle:", is_bipartite(triangle)[0])
def greedy_color(graph):
colors = {}
for u in graph:
used = {colors[v] for v in graph[u] if v in colors}
colors[u] = next(c for c in range(len(graph)) if c not in used)
return colors
print("Greedy colors:", greedy_color(triangle))Key points
- Bipartite means 2-colorable, which means no odd cycle
- BFS/DFS two-coloring runs in O(V + E)
- Finding the minimum number of colors is NP-hard
- Greedy coloring gives a valid, not always minimal, result