NP、NP 完全性與歸約
圖著色（graph coloring）
想像替一張地圖著色，使任何兩個共享邊界的國家都不同色。現在推廣：頂點是國家、邊是共享的邊界，你要給頂點著色，使相鄰的兩者永遠不同色。圖著色問：這張圖能否用至多 k 種顏色著色？它直接模擬避免衝突，例如分派考試時段，使任何學生都不會同時有兩場考試。
形式上，圖 G 的一個合法 k-著色，給每個頂點指派 k 種顏色之一，使得沒有任何邊連著兩個同色頂點。判定問題 k-COLORING 接收 G 與一個數 k，問是否存在這樣的著色。它屬於 NP：一個著色就是證書，驗證器在多項式時間內檢查每條邊，確認其兩端點不同色。能成功的最少顏色數稱為 G 的色數。
這裡的門檻鋒利又出人意料。2-COLORING 屬於 P：一張圖可二著色，當且僅當它是二部圖，你能以一次廣度優先掃描在線性時間內檢測。但 3-COLORING 是 NP 完全，由一個從 3-SAT 出發的小元件歸約證得。所以用兩色著色容易、用三色著色困難，正是我們在 SAT 看過的二到三的跳躍。連著名的四色定理（每張平面地圖至多需要四色）都救不了我們：判定一般圖是否可三著色仍是 NP 完全，連平面圖的三著色也是 NP 完全。著色是排程、編譯器的暫存器配置、頻率分派的主力模型。
一個三角形（三個頂點兩兩相連）需要 3 種顏色：任兩個都共享一條邊，所以三個都得不同。所以它可三著色但不可二著色。路徑 1-2-3-4 只需 2 種顏色（交替著色），所以可二著色；它確實是二部圖。
k-COLORING：用 k 色給頂點著色，使相鄰者不同色。二著色屬於 P（二部圖檢測）；三著色是 NP 完全。
二著色屬於 P（等價於是二部圖），但三著色是 NP 完全。四色定理為平面地圖定了上界，但它「並不」讓三著色變容易。
又稱
另見