그래프 색칠

그래프 이론에서 그래프 색칠(graph色漆, )은 그래프의 꼭지점들에, 같은 색이 인접하지 않도록 색을 부여하는 방법이다. 이를 사용하여 그래프의 불변량을 정의할 수 있다.

 정의 
(단순) 그래프 의 색칠 은 집합  및 함수 의 순서쌍이다. 이 경우, 임의의 변 에 대하여 이어야만 한다. 색칠 에서, 의 원소를 색(色, )이라고 한다.

그래프 의 두 색칠 , 이 주어졌을 때, 만약 전단사 함수 가 존재하여 인 경우, 두 색칠이 서로 동형이라고 한다.

그래프 의 변 색칠(邊色漆, )은 의 선 그래프 의 색칠이다. 평면 그래프 의 면 색칠(面色漆, )은 그 쌍대 그래프() 의 색칠이다.

 색칠 다항식과 색칠수 
섬네일|오른쪽|이 그래프 의 경우 이다.
그래프 에서, 색 을 공역으로 하는 색칠의 수를 라고 쓰자. (이 경우, 서로 동형인 색칠들도 중복하여 센다.) 만약 가 유한 그래프일 경우, 이는 에 대하여 다항식을 이루며, 이를 의 색칠 다항식()이라고 한다. 그래프 의 색칠수(色漆數, ) 는 색칠이 존재하는 최소의 정수이다.

마찬가지로, 변 색칠 다항식 · 변 색칠수 따위를 정의할 수 있다. 변 색칠수는 색칠 지표()라고도 하며, 로 쓴다.

 성질 
(단순) 유한 그래프 에 대하여, 다음 세 조건이 서로 동치다.

  ()
 이며 
(단순) 그래프 에 대하여, 다음 두 조건이 서로 동치다.

 는 이분 그래프이다.

모든 (단순) 유한 그래프 에 대하여, 다음이 성립한다.



여기서 는 의 최대 클릭의 크기이며, 는 의 꼭짓점들의 차수들의 최댓값이다.
브룩스의 정리()에 따르면, 임의의 연결 유한 그래프 에 대하여, 다음 두 조건이 서로 동치이다.
 이다.
 는 완벽 그래프이거나 홀수 크기의 순환 그래프이다.

4색정리에 따르면, 모든 유한 평면 그래프 에 대하여

이다. 그뢰치의 정리()에 따르면, 크기가 3인 순환을 갖지 않는 유한 평면 그래프 에 대하여

이다.

 색칠 다항식의 성질 
개의 꼭짓점을 갖는 그래프의 색칠 다항식은 차 다항식이다.

(단순) 유한 그래프 에 대하여, 다음 두 조건이 동치다.

 는 개의 꼭짓점을 갖는 나무이다.

(단순) 유한 그래프 에 대하여, 다음 두 조건이 동치다.

 는 크기 의 순환 그래프 이다.

섬네일|오른쪽|색칠 다항식이 인 그래프
두 그래프의 색칠 다항식이 같을 경우, 이들이 색칠 동치()라고 한다. 서로 동형이 아닌 두 그래프가 색칠 동치일 수 있다. 예를 들어, 꼭짓점의 수가 같지만 서로 동형이 아닌 두 나무는 색칠 동치이다. 또한, 색칠 다항식이 인 그래프는 총 3개가 있다.

연결 성분 으로 구성된 그래프의 색칠 다항식은 다음과 같다.

(단순) 그래프  및 에 대하여, 를 에서 변 를 제거한 그래프, 를 에서 변 를 제거하고 와 를 합친 그래프라고 하자. 그렇다면 다음이 성립한다.

즉, 이를 사용하여 색칠 다항식을 재귀적으로 계산할 수 있다.

 알고리즘 
임의의 그래프에 대하여 -색칠이 존재하는지 여부는 NP-완전 결정 문제다. 이는 리처드 카프가 1972년에 보인 21개의 NP-완전 문제 중의 하나이다.

임의의 그래프 에 대하여, -색칠은 항상 존재하며, 탐욕 알고리즘으로 쉽게 찾을 수 있다.

 예 
일부 그래프의 색칠 다항식 및 색칠수는 다음과 같다.
 다항식  색칠 다항식  색칠수 변이 없는 그래프     1 완전 그래프      개의 꼭짓점을 갖는 나무      2 순환 그래프    2 ( 짝수), 3 ( 홀수) 페테르센 그래프    3

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

스도쿠 역시 일종의 그래프 색칠 문제이다. 이 경우, 9×9 격자의 각 행·각 열·각 3×3 부분격자는 클릭을 이루며, 스도쿠는 주어진 부분적 9-색칠을 완성시키는 문제이다.

 외부 링크 


 같이 보기 
 텃 다항식
 램지의 정리


분류:그래프 이론의 계산 문제
분류:NP-완전 문제
분류:NP-난해 문제