그래프 색칠(3색칠)

그래프의 꼭짓점에 색을 칠하되 변으로 이어진 두 꼭짓점은 색이 다르게 하는 문제다. 두 색으로 되는지는 쉽게 판정할 수 있지만(P), 세 색으로 되는지 묻는 3색칠 문제는 NP-완전이다. 색칠 결과를 받으면 변마다 양 끝의 색이 다른지만 보면 되므로 검증은 쉽다. 시간표 짜기, 주파수 배정 같은 실제 문제가 그래프 색칠로 표현된다. 평면 지도는 네 색이면 언제나 칠할 수 있지만(4색 정리), 세 색으로 되는지 판정하는 것은 평면 그래프에서도 NP-완전이다.