완벽 그래프
정의
그래프 $G$ 의 모든 유도 서브 그래프 $H$ 가 다음을 만족하면 완벽 그래프라 한다. $$ \chi (H) = \omega (H) $$
설명
그래프 이론의 세계는 수학의 많은 분과가 그러하듯 어마어마하게 넓은데, 솔직히 조금은 더 넓다고 말하고 싶다. 그래프에서 버텍스와 에지를 정의하는 방법이 너무 다양하기 때문이다. 영인자 그래프는 물론, 구간 그래프처럼 딱히 그래프가 아니었어도 상관없었을 무언가를 가져와도 그래프는 그래프다.
단, 그것이 가치있는가는 별개의 문제다. 그래프에서 연구의 가치가 있는 경우로 가장 쉽게 생각할 수 있는 것은 역시 그래프 컬러링이나 연결성, 거리적 성질등에 대한 내용이다. 그냥 그래프가 정의되기만 한다면 그다지 큰 관심을 받기가 힘들다.
완벽 그래프는 그 중에서도 그래프 컬러링에 특히 관심을 두는 의미에서 완벽한 그래프라고 볼 수 있다. 모든 그래프 $H$ 는 클리크 수 $\omega (H)$ 에 대해 당연히 $$ \omega (H) \le \chi (H) $$ 이다. 어떤 그래프든 서브클리크 $K_{n}$ 가 존재하면 당연히 그들끼리는 $n-1$ 가지의 색으로 칠할 수 없기 때문이다. 완벽 그래프는 위의 조건에서 부등호인 경우를 배제한 것으로, 클리크가 아닌 이상은 반드시 더 적은 색으로 칠할 수 있다.
순수한 그래프 이론은 조합론의 한 분과로 보는 시각이 있고, 조합에 대한 문제에서는 이러한 완벽 그래프 같은 개념이 항상 등장할 수밖에 없다.