그래프 색칠: 두 판 사이의 차이

그래프 <math>\Gamma</math>에서, 색 <math>C=\{1,2,\dots,t\}</math>을 공역으로 하는 색칠의 수를 <math>P_\Gamma(t)</math>라고 쓰자. (이 경우, 서로 동형인 색칠들도 중복하여 센다.) 이는 <math>t</math>에 대하여 [[다항식]]을 이루며, 이를 <math>\Gamma</math>의 '''색칠 다항식'''({{llang|en|chromatic polynomial}})이라고 한다. 그래프 <math>\Gamma</math>의 '''색칠수'''(色漆數, {{llang|en|chromatic number}}) <math>\chi(\Gamma)</math>는 색칠이 존재하는 최소의 정수이다.

:<math>\chi(\Gamma)=\min\{t\in\mathbb N\colon P_\Gamma(t)>0\}</math>

 

== 성질 ==