그래프 색칠 문제

위키백과 ― 우리 모두의 백과사전.

꼭지점 6개인 그래프를 빨강, 녹색, 파랑의 세 가지 색으로 꼭지점을 칠하였다. 이 경우 두 개의 색으로는 불가능하다.

그래프 색칠 문제는 그래프의 꼭지점이나 변과 같은 부분에 각각 색을 칠하는 문제로, 이때 색을 칠하는 방법에 여러가지 제약이 가해진다. 예를 들어, 그래프의 꼭지점에 색을 칠하면서 인접한 두 꼭지점에는 다른 색을 할당하는 문제가 될 수 있다.

일반적으로는 그래프의 꼭지점에 색을 할당하는 문제를 주로 다루며, 변에 색을 할당하는 문제의 경우 라인 그래프의 꼭지점 색칠 문제로 바꿀 수 있다. 평면 그래프의 경우 면에 색을 칠하는 문제를 생각할 수 있는데, 이 또한 듀얼 그래프의 꼭지점 색칠 문제로 변환이 가능하다.

그래프를 색칠하는 문제는 많은 분야에 응용이 되고 있다. 예를 들어 컴파일러에서 프로세서 레지스터를 할당하는 문제, 무선 기지국 사이에서 간섭을 없애기 위한 주파수 할당 문제 등에 이용된다.

[편집] 색칠수

그래프의 색칠수(채색수, chromatic number)는 그 그래프를 색칠하는 데에 필요한 최소한의 수를 의미한다. 즉, 그래프 $G$ 의 색칠수가 $k$ 일 경우 $k - 1$ 개 이하의 색으로는 그 그래프를 칠할 수 없지만 $k$ 개로는 칠할 수 있다. 보통 그래프 $G$ 의 색칠수를 $χ(G)$ 로 표기한다.

예를 들어, $n$ 개 꼭지점을 가진 완전 그래프의 색칠수는 $n$ 이다.

특정 그래프가 $k$ 개 색으로 색칠될 수 있는가를 푸는 결정 문제는 리처드 카프가 1972년에 보인 21개의 NP-완전 문제 중의 하나이다.