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

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

정의

루프가 없는 그래프 $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$-크로마틱 그래프라 한다.


설명

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

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

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

정리 1


  1. Wilson. (1970). Introduction to Graph Theory: p82. ↩︎

댓글