Graph Coloring

← Back to NP-Complete

Assign colors to graph vertices such that no two adjacent vertices share the same color. Determining if a graph is k-colorable is NP-Complete for k >= 3. Applications include register allocation in compilers, scheduling, and map coloring.

computational-complexity complexity-classes np-complete graph-coloring