Colors vertices so no adjacent vertices share same color
Time: O(V × 2ⱽ)
Space: O(2ⱽ)
Use Case: Scheduling, register allocation, frequency assignment
Algorithm Execution
Select an algorithm and generate steps to begin visualization
About Graph Coloring
Graph coloring assigns colors to vertices so that no two adjacent vertices share a color, using as few colors as possible. The minimum number needed is the chromatic number, and computing it is NP-hard for general graphs.
How it works
The greedy algorithm orders the vertices and gives each one the smallest color not used by its already-colored neighbors, guaranteeing at most one more color than the maximum degree. Orderings such as Welsh-Powell (by decreasing degree) or DSatur (by saturation, the number of distinct neighbor colors) often use far fewer colors in practice. Exact coloring uses backtracking with pruning, feasible only for small graphs.
Applications
Coloring schedules exams so no student has two at once, allocates CPU registers in compilers, assigns radio frequencies without interference, and colors maps so neighboring regions differ. The four color theorem for planar graphs is one of the most celebrated results in mathematics. Bipartite checking is exactly 2-colorability.