Colorability Complexity for Planar Graphs

A planar graph is one that you can draw on paper without edge crossings. Example: K_3,2 vs. K_3,3.

Complexity of determining k-colorability for planar graphs as a function of k:

• 1: O(1) (can't do it if there are any edges at all).
• 2: O(|V|+|E|) (BFS!).
• 3: NP-complete (special widget to take general reduction and eliminate edge crossings).
• 4: O(1) (famous 4-color map theorem, always ``yes'').

The number 3 comes up in many NP-complete problems!