이번 글에서는 그래프이론의 clique number에 대해 알아보자. 그리고 지난 글에서 chromatic number에 대해 얘기하였었는데 chromatic number와 clique number의 관계에 대해서도 알아보자. 참 재밌는 결과들이 있으니까 clique number와 chromatic number의 관계를 꼭 알아보도록 하자. 그러면 이제 시작해보자.
clique number
그래프 $G$가 있다고 하자. clique number의 기호는 $\omega(G)$라고 하겠다. 그래프 $G$에 pairwise하게 adjacent vertices 들로 구성된 set이 있을것이다. 이러한 집합을 clique set이라고 하는 것은 알고 있을 테다. clique number라는 것은 이러한 clique set의 크기중 최대값을 의미한다. 여기서 그래프 $G$의 independence number를 $\alpha(G)$라고 썼던 것을 상기해보자. $\alpha(G)$는 independent set 의 크기중 가장 큰 값을 의미한다. $\alpha$는 그리스어 알파벳중에서 맨 처음에 나오는 알파벳이다. clique number에 사용되는 $\omega$는 그리스어 알파벳중에서 맨 마지막에 나오는 알파벳이다.
chromatic number와 clique number 관계
그래프 $G$가 있다고 하자. chromatic number는 $\chi(G)$라고 표시한다. 그리고 independent number는 $\alpha(G)$라고 표시한다. 그리고 clique number 는 $\alpha(G)$라고 표시한다. 이 때 chromatic number, independent number 그리고 clique number의 관계는 아래와 같다.
$$\chi(G) \geq \omega(G) , \chi(G) \geq \frac{n(G)}{\alpha(G)}$$
증명) 첫번째 bound는 성립한다. 왜냐하면 clique내의 vertices들은 다른 색을 가지기 때문이다. 두번째 바운드 또한 성립한다. 각각의 color class는 independent set 이다 그래서 최대 $\alpha(G)$의 원소들을 갖는다. 그러므로 bound 둘다 성립한다.
$\chi(G)$는 $\omega(G)$보다도 클 수 있다. $r\geq 2$라고 하자. 그리고 $G$를 $C_{2r+1}$과 $K_s$의 join이라고 하자. $C_{2r+1}$는 삼각형을 갖지 않는다. 그래서 $\omega(G) = s+2$이다. induced cycle $C_{2r+1}$을 properly coloring 하는데는 적으도 세개의 색이 필요하다. $s-$clique 는 s개의 색이 필요하다. $C_{2r+1}$의 모든 vertex 는 clique와 adjacent 하다. 이 s개의 색은 처음세개와 달라야 한다. 따라서 $\chi(G) \geq s+3$이다. 그러므로 $\chi(G) > \omega(G)$이다.