완벽 그래프

위키백과 ― 우리 모두의 백과사전.

그래프 이론에서 어떤 그래프 G가 완벽 그래프(perfect graph)란 꼭지점 집합의 모든 부분집합 X에 대해서, G에서 X에 속한 꼭지점을 지워서 만든 부분 그래프 H는 색칠수 χ(H)가 완전모임수 ω(H)와 같다는 뜻이다. 어떤 그래프 G가 완전모임수 ω(G) 값이 k라 함은 그 그래프의 부분그래프 중에 꼭지점 k개 미만인 완전 그래프는 없지만 꼭지점 k개인 완전 그래프는 있다는 뜻이다.

꼭지점 k개짜리 완전 그래프를 색칠하려면 k개 색깔이 필요하므로 ω(G)≤χ(G)라는 사실은 쉽다. 하지만 어떤 그래프의 경우 등호가 성립하지 않는다. 예를 들면 C₅를 꼭지점 5개짜리 회로인 그래프라고 할때 χ(C₅)=3이지만 ω(C₅)=2이다. 이것으로 알 수 있는 사실 중 하나는 C₅는 완벽 그래프가 아니라는 점이다. 같은 논리로 모든 홀수 길이의 회로는 완벽 그래프가 아님을 쉽게 알 수 있다.

[편집] 완벽 그래프로 알려져있는 그래프들

몇몇 잘 알려진 그래프들은 완벽 그래프임이 잘 알려져 있다.

[편집] 완벽 그래프의 특성

완벽 그래프가 어떤 그래프들인지 정확하게 파악하는 문제는 오랫동안 수학자들을 괴롭힌 어려운 문제였다.

완벽 그래프 정리 (1972, 로바스 (László Lovász))

어떤 그래프가 완벽 그래프일 필요충분조건은 그 그래프의 complement가 완벽 그래프라는 것이다.

강한 완벽 그래프 정리 (2002, 추드노프스키, 로버트슨, 씨이머, 토마스)

그래프가 완벽 그래프일 필요충분조건은 홀수 길이의 회로나 그 complement를 induced 부분 그래프로 가지지 않는다는 것이다.

강한 완벽 그래프 정리는 1960년에 클라우드 버지(Claude Berge)가 처음 제기한 것인데, 40년이상 미해결난제였다. 증명은 길고 복잡하다. 한편 강한 완벽 그래프 정리를 이용하면 완벽 그래프 정리를 쉽게 증명할 수 있다. 강한 완벽 그래프 정리가 증명된 이후 어떤 그래프가 완벽 그래프인지 확인하는 다항식 시간 알고리즘이 발견되었다.