243. What is graph coloring, and what does the four color theorem say?
MediumGraph algorithms
Technical
Show model answer
A proper coloring assigns colors so adjacent vertices differ; the chromatic number is the minimum colors needed. Deciding 2-colorability is easy (it means bipartite, checkable with BFS in O(V + E)), but deciding k-colorability for k ≥ 3 is NP-complete. Greedy coloring uses at most max degree + 1 colors, and ordering heuristics such as DSATUR often do better.
The four color theorem states that every planar graph (equivalently, every map of contiguous regions) can be colored with four colors. Its 1976 proof by Appel and Haken was the first major computer-assisted proof. Applications of coloring include register allocation, exam timetabling and frequency assignment.