평면 상에 교차점 없이 그릴 수 있는 그래프를 평면그래프라 한다. 모든 평면그래프는 이웃한 꼭지점이 서로 다른 색이 되도록 4개 이하의 색으로 잘 칠할 수 있다는 정리를 4색정리라고 하는데, 그래프이론에서 4색정리만큼 잘 알려지고 많은 사람들의 관심을 받은 문제는 없다고 해도 과언이 아니다. 이제 4색정리는 증명이 되었지만, 또 어떤 문제들이 남아있을까?
어떤 그래프 H가 그래프 G의 마이너라 함은, G에서 일부 변과 꼭지점을 지운 후 몇몇 변은 양 끝점을 한 점으로 합치는 ‘축약'(contraction) 연산을 해서 H가 얻어진다는 뜻이다. 어떤 그래프 G가 평면그래프라면 변 하나 잡아서 축약해도 여전히 평면에 교차점 없이 그릴 수 있기 때문에 평면그래프의 모든 마이너는 역시 평면그래프이다.
꼭지점 n개가 서로 다 이어진 그래프를 완전그래프라 부르고 Kn이라 한다. 하트비거는
“Kt+1이 마이너로 없는 모든 그래프는 이웃한 꼭지점은 다른 색이 되게 t개의 색으로 칠할 수 있다“
고 추측하였다. 휴고 하트비거(Hugo Hadwiger)가 1943년에 만든 추측이라서 하트비거의 추측(Hadwiger’s conjecture)이라고 부른다.
K5는 평면그래프가 아니기 때문에 평면그래프는 K5 마이너를 가질 수 없고 따라서 t=4일때 하트비거의 추측이 참이라면 벌써 4색 정리가 증명된다. 사실, 4색정리를 이용하면 t=4일때 하트비거의 추측 역시 증명할 수 있어서 t=4인 경우 이 추측은 4색정리와 동치이다.
t=2일때는 K3 마이너가 없는 그래프는 항상 수형도 여러 개로 구성된 그래프이므로 2개 색으로 쉽게 칠할 수 있다. t=3일때는 K4 마이너가 없는 경우인데, 이때는 series-parallel 그래프라는 그래프가 되어 역시 손쉽게 3개 색으로 칠할 수 있다.
한편 t=5인 경우는 어려운 문제인데, 1993년에 Robertson, Seymour, Thomas 세 명의 교수가 출판한 논문에서 t=5인 경우 최소 크기의 반례에서는 한 꼭지점을 잘 지우면 평면그래프가 된다는 것을 증명하였고 따라서 사색정리에 의해 t=5인 경우도 하트비거의 추측이 참이라는 것을 증명하였다.
이 추측은 t>5인 경우는 여전히 완전히 미해결인 상태로 남아있다.
이제 하트비거 추측을 약하게 만든 새로운 문제를 생각해보자. 하트비거의 추측이 맞다면 Kt+1마이너가 없는 그래프의 꼭지점 집합을 항상 t개의 꼭지점 집합 X1,X2, .., Xt로 잘 나눠서 각 X1,…,Xt 안에는 변이 하나도 포함되지 않게 할 수 있다. 그러면 혹시 잘 나눠서 각 Xi 안에서 각 꼭지점은 Xi 안에서는 f(t)개 이하의 이웃만 갖게 할 수 있을까? 만일 f(t)=0이라면 원래의 하트비거의 추측과 같다.
최근 필자가 KAIST 강동엽 학생, UIUC에서 박사학위 받고 잠깐 KAIST 와 있는 김재훈 박사, 그리고 프린스턴 대학 Seymour 교수 및 Edwards 학생과 함께 쓴 연구논문(arxiv에 올린 논문)에서 앞에서 언급한 하트비거의 추측의 약한 형태에 대해 연구를 하였는데, 위 조건을 만족하는 f(t)라는 함수가 존재한다는 것을 1페이지짜리 증명을 통해 풀었다. 여기서 흥미롭게도 이 약한 문제에서조차 t개가 아닌 t-1개로는 나눌 수 없다는 것 또한 증명할 수 있었다.