Mathematics/Olympiad (2) 썸네일형 리스트형 Introduction of Graph coloring : Chromatic number, Chromatic Polynomial, Acyclic Orientation ## Introduction Graph Coloring은 그래프에서 정점들을 색칠하며, 변으로 인접한 정점들이 서로 다른 색깔로 칠해지도록 하는 상황을 다룬다. 이러한 컬러링은 그래프 이론에서 상당히 중요하게 다루어지며, 4색정리와 같이 중요한 문제들의 소재가 되기도 했다. ## Chromatic Number Chromatic Number $\chi$는 Graph를 Coloring하는 것에 필요한 최소 색깔 수를 의미한다. 간단한 예시를 들자면, - $\chi = 1$인 경우, 그래프에는 변이 없다. - $\chi = 2$인 경우, 그래프는 이분그래프이다. 그래프의 정점의 개수를 $n$, 간선의 개수를 $m$이라 할 때, 다음 부등식이 성립한다. - $1 \le \chi \le n$. 1보다 큼은 자명하.. MO Checklist 이전 1 다음