18. Coloring

그래프에 겹치지 않게 색을 칠해본 경험 다들 있을 것이다. 이번 챕터에서는 이러한 색칠하기의 새로운 쓸모를 알아볼 수 있다. 스케줄링, 컴파일러 최적화, 공항 게이트 배정까지 — 생각보다 쓸모가 많다.

---

1. 동기: 스케줄링 문제

 6명의 과학자가 5개의 장비를 공유해야 한다. 같은 장비가 필요한 과학자들은 동시에 일할 수 없다. 최소 몇 개의 시간 블록이 필요할까?

 

 이걸 그래프로 모델링하면:

• Vertex = 과학자
• Edge = 충돌 (같은 장비 필요)
• Color = 시간 블록

 인접한 두 vertex(= 충돌하는 두 과학자)는 반드시 다른 색(= 다른 시간대)이어야 한다. 최소 몇 가지 색으로 칠할 수 있는지 구하면 답이 나온다.

---

2. 핵심 정의

Coloring: 함수 c: V → C

• C는 색의 집합
• 인접한 두 vertex x, y에 대해 반드시 c(x) ≠ c(y)

k-coloring: 정확히 k가지 색을 쓰는 coloring

Chromatic Number χ(G): G를 coloring 하는 데 필요한 최소 색 수

---

3. Clique와 Lower Bound

Clique (k-clique): 서로 전부 연결된 k개의 vertex 묶음 = Kₖ subgraph

위 사진에 A - B - C는 크기가 3인 clique이다.

 

k-clique 안의 vertex들은 서로 전부 인접하니까 전부 다른 색이 필요하다.

k-clique가 있으면 χ(G) ≥ k (lower bound)

 

---

4. Degree와 Upper Bound

 최대 degree가 k인 그래프에서는 어떤 vertex도 최대 k개의 이웃을 가진다. 따라서 이웃들이 쓰는 색을 피하면서 항상 하나의 색을 찾을 수 있다.

최대 degree가 k이면 χ(G) ≤ k+1 (upper bound)

 

두 bound를 합치면: k-clique 크기 ≤ χ(G) ≤ 최대 degree + 1

---

5. 특수 그래프들의 Chromatic Number

그래프	χ(G)	이유
Kₙ (완전 그래프)	n	모든 vertex가 서로 인접 → 전부 다른 색
Pₙ (path graph)	2	A-B-A-B-... 교대로 칠하면 됨
Tree	2	path graph의 일반화

 

---

6. 2-colorability와 Bipartite

Bipartite graph: vertex를 두 집합 A, B로 나눌 수 있고, 모든 edge가 A-B 사이에만 존재하는 그래프

판별법: A에 vertex 하나를 넣고, 그것과 연결된 것들을 B로, B와 연결된 것들을 다시 A로... 반복하다가 같은 집합 안에서 edge가 생기면 bipartite가 아니다.

 

3가지 동치 조건:

G가 2-colorable ⟺ G가 bipartite ⟺ G에 홀수 길이 cycle이 없다

 

예시:

A - B - C
|   |   |
D - E - F

• 집합 1: A, C, E
• 집합 2: B, D, F
• 모든 edge가 집합 1-2 사이 → Bipartite ✅ → χ(G) = 2

반면 삼각형(K₃)이 있으면 홀수 cycle → Not Bipartite → χ(G) ≥ 3

---

7. 4-Color Theorem

Planar graph: 평면에 edge가 교차하지 않게 그릴 수 있는 그래프. 지도를 그래프로 표현하면 planar graph가 된다.

4-Color Theorem: 모든 planar graph는 4-colorable → χ(G) ≤ 4

1976년 Appel & Haken이 컴퓨터의 도움을 받아 증명한 최초의 주요 정리다.

---

8. 응용

그래프 coloring은 충돌 관계를 모델링하는 데 강력하다.

• 컴파일러 최적화: CPU register 배정 문제 → vertex = 변수, edge = 동시에 살아있는 변수, color = register
• 공항 게이트 배정: vertex = 비행기, edge = 1시간 내 도착 충돌, color = gate

두 경우 모두 χ(G)를 구하면 필요한 최소 자원 수가 나온다.

---

9. 정리

개념	내용
Chromatic Number χ(G)	최소 색 수
Lower bound	k-clique 있으면 χ(G) ≥ k
Upper bound	최대 degree k이면 χ(G) ≤ k+1
2-colorable	⟺ Bipartite ⟺ 홀수 cycle 없음
4-Color Theorem	Planar graph → χ(G) ≤ 4