-그래프 정점(vertex) 집합과 간선(edge) 집합으로 이루어진 수학적 구조 -채색 그래프에서 같은 간선을 공유하는 정점을 서로 다른 색으로 칠하는 것 -그래프 $G$의 채색다항식 $=C_k(G)$ $k$개의 서로 다른 색을 사용하여 인접하는 두 정점은 같은 색이 아니게끔 그래프 $G$의 정점에 색칠하는 경우의 수 -채색수(chromatic number) $=\chi ( G)$ $C_k(G)\neq 0$ 을 만족하는 최소의 자연수 $k$값 ($C_k(G)$를 0에 가장 가깝게 하는 $k$) 영그래프 : 간선이 없는 그래프 영그래프의 채색다항식 $C_k(G)=K^n$ (인접한 정점이 없으므로 각 정점마다 k가지의 채색이 가능하다.) 영그래프의 채색수 $\chi ( G)$ $ = 1 $ (1가지의 색 ..
