VI. 그래프 이론 · 14/16

그래프 채색

채색수, 그리디 채색, 4색 정리

읽음 0/0 갱신 2026-07-05

개요 — 동기·문제의식

그래프 채색은 인접한 대상을 서로 다르게 표시하는 문제다. 지도에서 인접한 나라가 같은 색이면 안 되고, 동시에 열릴 수 없는 회의는 같은 시간대에 배정할 수 없으며, 서로 간섭하는 작업은 같은 자원을 공유할 수 없다.

그래프이론에서는 정점 채색과 변 채색을 구분한다. 정점 채색은 인접한 정점들이 다른 색을 갖게 하는 것이고, 변 채색은 인접한 간선들이 다른 색을 갖게 하는 것이다.¹

평면그래프 채색은 역사적으로 유명하다. 모든 planar graph는 4색으로 충분하지만, 그 정리의 증명은 컴퓨터 검증을 포함한다. 이 페이지에서는 손으로 증명 가능한 5색 정리를 자세히 다루고, Brooks 정리와 Vizing 정리를 안내한다.

직관

색은 실제 색깔이 아니라 충돌하지 않는 label이다. 색수가 작다는 것은 복잡한 관계망을 적은 수의 독립집합으로 나눌 수 있다는 뜻이다.

정점 채색에서 한 색깔의 정점들은 서로 인접하지 않는다. 따라서 $k$-coloring은 정점집합을 $k$개의 independent set으로 분할하는 것과 같다.

변 채색은 line graph로 바꿔 정점 채색처럼 볼 수 있다. $G$ 의 간선을 정점으로 만든 그래프 $L(G)$ 에서, 인접한 간선끼리 인접하게 두면 $G$ 의 변 채색은 $L(G)$ 의 정점 채색이다.

정의

정점 $k$-채색: 함수 $c:V(G)\to\{1,\dots,k\}$ 로서 $uv\in E(G)$ 이면 $c(u)\ne c(v)$.

색수(chromatic number): 가능한 최소 $k$ 를 $\chi(G)$ 라 쓴다.

$k$-chromatic: $\chi(G)=k$ 인 그래프.

변 $k$-채색: 함수 $c:E(G)\to\{1,\dots,k\}$ 로서 인접한 두 간선은 다른 색을 갖는다.

chromatic index: 가능한 최소 변 색수, $\chi'(G)$.

그래프	색수
empty graph	1 또는 정점 없으면 0 관례
$K_n$	$n$
$P_n$ ($n\ge2$)	2
$C_{2r}$	2
$C_{2r+1}$	3
nontrivial bipartite graph	2 이하

list coloring: 각 정점마다 허용 색 목록이 따로 주어졌을 때의 채색. choice number는 list coloring의 최소 목록 크기다.

주요 정리

정리 1 (greedy bound). 모든 그래프는 $\Delta(G)+1$ 색으로 정점 채색할 수 있다.

증명 보기

증명. 정점을 임의 순서로 하나씩 칠한다. 현재 정점의 이미 칠해진 이웃은 최대 $\Delta(G)$ 개이므로, $\Delta(G)+1$ 색 중 적어도 하나는 남는다. ∎

정리 2 (5색 정리). 모든 planar graph는 5-colorable이다.²

증명 보기

증명. 정점 수에 대한 귀납. Euler 부등식으로 planar graph에는 차수 5 이하 정점 $v$ 가 있다. $G-v$ 를 귀납가정으로 5색칠한다. $v$ 의 이웃들이 4색 이하만 쓰면 남은 색을 $v$ 에 주면 된다.

남은 경우는 $v$ 의 차수가 정확히 5이고, 이웃 $v_1, v_2, v_3, v_4, v_5$ 가 $v$ 둘레의 순서대로 각각 색 $1,2,3,4,5$ 를 쓰는 경우다. 색 1과 3만으로 유도된 부분그래프를 보자. $v_1$ 과 $v_3$ 이 같은 connected component에 없으면, $v_1$ 이 속한 component에서 색 1과 3을 맞바꾼다. 그러면 $v$ 주변에 색 1이 사라져 $v$ 를 색 1로 칠할 수 있다.

따라서 $v_1$ 과 $v_3$ 이 1-3 Kempe chain으로 연결되어 있다고 하자. 이 path와 간선 $vv_1$, $vv_3$ 는 평면에서 Jordan curve를 만들고, 이 곡선은 $v_2$ 와 $v_4$ 를 서로 다른 쪽에 놓는다. 그러므로 색 2와 4만 쓰는 path가 $v_2$ 와 $v_4$ 를 연결할 수 없다. $v_2$ 의 2-4 component에서 색 2와 4를 맞바꾸면 $v$ 주변에 색 2가 사라진다. 따라서 $v$ 를 색 2로 칠한다. ∎

정리 3 (4색 정리, 안내). 모든 planar graph는 4-colorable이다.³

설명. 4색 정리는 5색 정리보다 훨씬 어렵고, 알려진 증명은 큰 경우 분류와 컴퓨터 검증을 포함한다. 이 위키에서는 정리의 위치와 활용만 안내한다.

정리 4 (Brooks 정리). 연결 그래프 $G$ 가 complete graph도 odd cycle도 아니면 $$\chi(G)\le\Delta(G).$$

의미. greedy bound $\Delta+1$ 이 정말 필요한 경우는 완전그래프와 홀수 순환뿐이라는 강한 정리다.⁴

정리 5 (Vizing 정리). 단순 그래프 $G$ 에 대해 $$\Delta(G)\le\chi'(G)\le\Delta(G)+1.$$

의미. 정점 채색은 매우 거칠 수 있지만, 변 채색은 최대차수와 최대차수+1 중 하나로만 결정된다.⁵

예제

예제 1 ($K_n$). 모든 정점이 서로 인접하므로 색이 모두 달라야 한다. $\chi(K_n)=n$.

예제 2 ($C_5$). 홀수 순환은 2색칠이 불가능하다. 세 번째 색을 쓰면 가능하므로 $\chi(C_5)=3$.

예제 3 ($K_{3,3}$). 이분그래프이므로 정점 색수는 2다. 그러나 planar가 아니므로 4색 정리나 5색 정리의 쉬운 예는 아니다.

예제 4 (Petersen 그래프). Petersen 그래프는 triangle-free지만 3-chromatic이다. clique number만으로 색수를 결정할 수 없음을 보여준다.

예제 5 (planar triangulation). maximal planar graph는 많은 삼각형을 가지므로 2색칠은 불가능하고, 3색 또는 4색이 필요할 수 있다. 그래도 4색 정리에 의해 4색이면 충분하다.

예제 6 (별 $K_{1,n}$ 의 변 채색). 중심에 incident한 $n$개 간선은 서로 모두 인접한 간선들이므로 서로 다른 색이 필요하다. $\chi'(K_{1,n})=n=\Delta$.

예제 7 (홀수 순환의 변 채색). $C_{2r+1}$ 의 변 채색은 3색이 필요하다. 최대차수는 2이므로 Vizing 정리의 class 2 사례다.

예제 8 (스케줄링). 회의를 정점, 동시에 참석해야 하는 사람이 겹치는 회의쌍을 간선으로 두면 색수는 필요한 최소 시간대 수다.

흔한 오해와 함정

색의 이름에 의미를 부여하기 — 색은 label이다. 빨강·파랑 같은 실제 의미는 없다.
clique number가 항상 색수와 같다고 생각하기 — Petersen류, Erdős의 large girth high chromatic graph가 반례다.
4색 정리를 쉽게 증명할 수 있다고 기대하기 — 5색 정리는 짧은 Kempe chain 논법으로 되지만, 4색은 역사적으로 전혀 다른 난이도다.
정점 채색과 변 채색을 섞기 — 색수 $\chi$ 와 chromatic index $\chi'$ 는 다른 불변량이다.
greedy algorithm이 항상 최적이라고 생각하기 — 정점 순서가 나쁘면 필요한 것보다 많은 색을 쓸 수 있다.
planar graph가 항상 3-colorable이라고 생각하기 — $K_4$ 는 planar이고 4-chromatic이다.

큰 그림 / 연결

planar graphs euler는 5색 정리의 핵심 입력을 준다. Euler 부등식이 차수 5 이하 정점의 존재를 보장하고, 그 정점을 제거하는 귀납이 작동한다.

extremal and ramsey에서는 색수가 부분그래프 강제와 연결된다. Turán 정리는 $K_r$ 를 피하는 그래프의 최대 간선 수를 주고, Erdős-Stone 정리는 극단 밀도가 금지 그래프의 색수에 의해 결정됨을 말한다.

확률적 방법는 큰 색수를 갖지만 국소적으로는 tree처럼 보이는 그래프를 만든다. 이는 "큰 색수에는 큰 clique가 있어야 한다"는 잘못된 직관을 깨뜨린다.

spectral graph theory에서는 인접행렬 고유값으로 색수를 하한 또는 상한 추정하는 방법이 있다. 이는 linear-algebra 위키 eigenvalues-and-characteristic-polynomial의 응용이다.

연습문제

$K_n$, $P_n$, $C_n$ 의 색수를 구하라.
이분그래프가 2-colorable임을 정의로 증명하라.
$C_{2r+1}$ 이 2-colorable이 아님을 보이라.
greedy bound $\chi(G)\le\Delta(G)+1$ 을 증명하라.
Euler 부등식으로 planar graph에 차수 5 이하 정점이 있음을 보이라.
5색 정리 증명에서 Kempe chain 색 교환이 proper coloring을 보존하는 이유를 설명하라.
$K_4$ 가 planar이지만 4-chromatic임을 확인하라.
$K_{m,n}$ 의 chromatic index를 추측하고 작은 예로 검산하라.
Vizing 정리에서 홀수 순환이 왜 $\Delta+1$ 쪽인지 설명하라.

힌트 / 정답

$\chi(K_n)=n$, $\chi(P_n)=2$ for $n\ge2$, $\chi(C_n)=2$ if $n$ even and $3$ if $n$ odd.
두 part에 서로 다른 색을 주면 같은 part 안에는 간선이 없으므로 proper coloring이다.
두 색을 번갈아 칠하면 홀수 길이 때문에 마지막 정점이 첫 정점과 같은 색이 되어 충돌한다.
이미 칠한 이웃이 최대 $\Delta$ 개이므로 $\Delta+1$ 색 중 하나는 사용 가능하다.
모든 정점 차수가 6 이상이면 평균 차수도 6 이상인데, planar graph는 평균 차수 $<6$ 이다.
두 색 $i,j$ 만 쓰는 component 안에서 $i$와 $j$를 맞바꾸면, 그 component 내부의 간선은 여전히 서로 다른 색이고 바깥과 닿는 간선도 같은 색 충돌이 생기지 않는다.
$K_4$ 는 삼각형 안에 네 번째 정점을 넣어 그릴 수 있다. 네 정점이 모두 서로 인접하므로 색은 4개 필요하다.
König의 edge coloring theorem으로 bipartite graph는 $\chi'(G)=\Delta(G)$ 이다. 따라서 $K_{m,n}$ 은 $\max(m,n)$.
$C_{2r+1}$ 에서 간선을 두 색으로 번갈아 칠하면 홀수 개라 마지막 간선이 첫 간선과 충돌한다. 세 색이면 가능하다.

각주

diestel §5.1–5.3 [synthesis] — vertex coloring, chromatic number, edge coloring, chromatic index의 정의. ↩
diestel §5.1, Proposition 5.1.2 [synthesis] — Five Colour Theorem과 Kempe chain 증명. ↩
diestel §5.1, Theorem 5.1.1 [synthesis] — Four Colour Theorem의 진술과 역사적 위치. ↩
diestel §5.2, Theorem 5.2.4 [synthesis] — Brooks theorem. ↩
diestel §5.3, Theorem 5.3.2 [synthesis] — Vizing theorem과 class 1/class 2 구분. ↩