📂그래프이론

그래프 컬러링과 브룩스 정리

정의

루프가 없는 그래프 $G$ 에 대해 다음과 같은 함수 $f : V(G) \to [k]$ 를 $G$ 의 $k$-컬러링이라 한다. $$ u \sim v \implies f(u) \ne f(v) $$ 그래프 $G$ 가 $k$-컬러링을 가지면 $k$-채색가능이라도 한다. 만약 $k$-채색가능인데 $(k-1)$-채색가능하지 않으면 그 $k$ 를 $G$ 의 크로마틱 수^{chromatic number}라 부르고 $\chi(G) = k$ 와 같이 나타낸다. 크로마틱 수가 $k$ 인 그래프를 $k$-크로마틱 그래프라 한다.

---

• 루프 란 버텍스 $u$ 가 스스로와 인접한 에지를 말한다.
• $[k] = \left\{ 1, \cdots , k \right\}$ 는 $1$ 부터 $k$ 까지의 자연수를 모아놓은 집합을 의미한다. 여기서 자연수라는 것에는 큰 의미가 없고, $k$ 개의 다른 원소면 추상적으로 컬러링의 공역이 될 수 있다. 가령 $[3] = \left\{ \text{red}, \text{blue}, \text{black} \right\}$ 이어도 상관 없지만, $\left\{ 1,2,3 \right\}$ 과 본질적으로 다를 게 없기 때문에 자연수를 쓰는 것이다.

설명

그래프 컬러링을 우리말로 설명하자면 인접한 버텍스끼리 다른 색에 채색―매핑하는 것을 말한다. 그러한 함수는 수없이 존재할 수 있으므로 당연히 우리의 관심사가 되는 것은 최소한의 채색이 될 것이고, 따라서 채색가능이라는 표현은 거의 쓰이지 않는다.

그래프의 크로마틱 수를 판별하는 문제는 조합론에서 늘 관심을 받아왔으며, 그 중에서도 유명한 것이 한때 난제로 악명 높았던 4색 문제다. 일반적으로 이러한 문제들은 NP 문제로, 지금도 기발한 알고리즘과 정리들의 증명을 기다리고 있다.

임의의 그래프에 대해서 가장 쉽게 생각할 수 있는 채색은 그냥 $n$ 개의 버텍스를 $n$ 개의 서로 다른 색으로 칠하는 것이다. 이러한 채색을 그리디 컬러링이라 하는데, 당연히 가장 어리석은 방법이다. 그래프의 성질에 따라 다음과 같이 다양한 정리가 알려져있다. 그래프 컬러링을 접할 때 가장 먼저 접하게 되고 가장 유명한 정리는 이 중에서도 브룩스 정리다.

정리 ¹

• [1]: 컴플리트 그래프: $K_{n}$ 과 널 그래프 $G$ 에 대해 $$ \chi(K_{n}) = n \\ \chi(G) = 1 $$
• [2]: $G$ 가 널 그래프가 아닌 이분 그래프인 것과 $\chi(G) = 2$ 인 것은 동치다.
• [3]: 심플 그래프 $G$ 의 가장 큰 차수를 $\Delta (G)$ 라고 하면 $$ \chi(G) \le \Delta (G) +1 $$
• [4]: $G$ 의 에지의 수를 $m$ 이라고 하면 $$ \chi(G) \le \sqrt{2m+1/4}+1/2 $$
• [5] 브룩스 정리: 심플 연결 그래프 $G$ 가 컴플리트 그래프가 아니고 최대 차수가 $\Delta (G) \ge 3$ 면 $G$ 는 $\chi(G) \le \Delta (G)$