그래프 색칠

그래프의 3개의 색으로의 색칠. 이 그래프는 2개의 색으로 색칠할 수 없으며, 따라서 이 그래프의 색칠수는 3이다.

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

정의

(단순) 그래프 $G$의 색칠 $(C,c)$은 집합 $C$ 및 함수 $c:V(G)\to C$의 순서쌍이다. 이 경우, 임의의 변 $v_1{v}_2\in E(G)$에 대하여 $c(v_1)\ne c(v_2)$이어야만 한다. 색칠 $(C,c)$에서, $C$의 원소를 색(色, 틀:Llang)이라고 한다.

그래프 $G$의 두 색칠 $(C,c)$, $(C^{\prime },c^{\prime })$이 주어졌을 때, 만약 전단사 함수 $f:C\to C^{\prime }$가 존재하여 $c^{\prime }=f\circ c$인 경우, 두 색칠이 서로 동형이라고 한다.

그래프 $G$의 변 색칠(邊色漆, 틀:Llang)은 $G$의 선 그래프 $L(G)$의 색칠이다. 평면 그래프 $G$의 면 색칠(面色漆, 틀:Llang)은 그 쌍대 그래프(틀:Llang) $G^{\prime }$의 색칠이다.

색칠 다항식과 색칠수

이 그래프 $G$의 경우 $P_{G}a(3)=12$이다.

그래프 $G$에서, 색 $C=\{1,2,\dots ,t\}$을 공역으로 하는 색칠의 수를 $P_G(t)$라고 쓰자. (이 경우, 서로 동형인 색칠들도 중복하여 센다.) 만약 $G$가 유한 그래프일 경우, 이는 $t$에 대하여 다항식을 이루며, 이를 $G$의 색칠 다항식(틀:Llang)이라고 한다. 그래프 $G$의 색칠수(色漆數, 틀:Llang) $\chi (G)$는 색칠이 존재하는 최소의 정수이다.

$\chi (G)=\min \{t\in \mathbb{N}:P_G(t)>0\}$

마찬가지로, 변 색칠 다항식 · 변 색칠수 따위를 정의할 수 있다. 변 색칠수는 색칠 지표(틀:Llang)라고도 하며, ${\chi }^{\prime }(G)$로 쓴다.

성질

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

• $\chi (G)=1$
• $P_G(t)=t^n$ ($n\in {\mathbb{Z}}^{+}$)
• $|E(G)|=0$이며 $|V(G)|\ge 1$

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

• $\chi (G)=2$
• $G$는 이분 그래프이다.

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

• $1\le \chi (G)\le |V(G)|$
• $\chi (G)(\chi (G)-1)\le 2|E(G)|$
• $\omega (G)\le \chi (G)\le \mathrm{\Delta }(G)+1$

여기서 $\omega (G)$는 $G$의 최대 클릭의 크기이며, $\mathrm{\Delta }(G)=\underset{v\in V(G)}{\max }\mathrm{deg}v$는 $G$의 꼭짓점들의 차수들의 최댓값이다. 브룩스의 정리(틀:Llang)에 따르면, 임의의 연결 유한 그래프 $G$에 대하여, 다음 두 조건이 서로 동치이다.

• $\chi (G)=\mathrm{\Delta }(G)+1$이다.
• $G$는 완벽 그래프이거나 홀수 크기의 순환 그래프이다.

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

$\chi (G)\le 4$

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

$\chi (G)\le 3$

이다.

색칠 다항식의 성질

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

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

• ${\chi }_G(t)=t(t-1{)}^{n-1}$
• $G$는 $n$개의 꼭짓점을 갖는 나무이다.

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

• ${\chi }_G(t)=(t-1{)}^n+(-1{)}^n(t-1)$
• $G$는 크기 $n$의 순환 그래프 $C_n$이다.

색칠 다항식이 $t(t-1{)}^3(t-2)$인 그래프

두 그래프의 색칠 다항식이 같을 경우, 이들이 색칠 동치(틀:Llang)라고 한다. 서로 동형이 아닌 두 그래프가 색칠 동치일 수 있다. 예를 들어, 꼭짓점의 수가 같지만 서로 동형이 아닌 두 나무는 색칠 동치이다. 또한, 색칠 다항식이 $t(t-1{)}^3(t-2)$인 그래프는 총 3개가 있다.

연결 성분 $G_1,\dots ,G_n$으로 구성된 그래프의 색칠 다항식은 다음과 같다.

$P_G(t)=\prod _{i=1}^n{P}_{G_i}(t)$

(단순) 그래프 $G$ 및 $uv\in E(G)$에 대하여, $G-uv$를 $G$에서 변 $uv$를 제거한 그래프, $G/uv$를 $G$에서 변 $uv$를 제거하고 $u$와 $v$를 합친 그래프라고 하자. 그렇다면 다음이 성립한다.

$P_G=P_{G-uv}-P_{G/uv}$

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

알고리즘

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

임의의 그래프 $G$에 대하여, $\mathrm{\Delta }(G)+1$-색칠은 항상 존재하며, 탐욕 알고리즘으로 쉽게 찾을 수 있다.

예

일부 그래프의 색칠 다항식 및 색칠수는 다음과 같다.

다항식	색칠 다항식	색칠수
변이 없는 그래프 ${\overline{K}}_n$	$t^n$	1
완전 그래프 $K_n$	$t(t-1)(t-2)...(t-(n-1))$	$n$
$n$개의 꼭짓점을 갖는 나무	$t(t-1{)}^{n-1}$	2
순환 그래프 $C_n$	$(t-1{)}^n+(-1{)}^n(t-1)$	2 ($n$ 짝수), 3 ($n$ 홀수)
페테르센 그래프	$t(t-1)(t-2)(t^7-12t^6+67t^5-230t^4+529t^3-814t^2+775t-352)$	3

응용

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

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

외부 링크

• 틀:Eom

같이 보기

• 텃 다항식
• 램지의 정리