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

* <math>1\le\chi(\Gamma)\le|V(\Gamma)|</math>

* <math>\chi(\Gamma)\left(\chi(\Gamma)-1\right)\le2|E(\Gamma)|</math>

여기서 <math>\omega(\Gamma)</math>는 <math>\Gamma</math>의 최대 [[클릭 (그래프 이론)|클릭]]의 크기이며, <math>\Delta(\Gamma)</math>는 <math>\Gamma</math>의 꼭짓점들의 차수들의 최댓값이다.

 

* <math>\chi(G)\ge 3</math> : 그래프 <math>G</math>가 홀수 길이의 [[회로]]를 가진다(또는, <math>G</math>가 [[이분 그래프]]가 아니다).

* <math>G</math>가 [[완전 그래프]]가 아니거나 홀수 길이의 , <math>\chi(G)\le\Delta(G)</math> (브룩의 정리)

* <math>G</math>가 [[평면 그래프]]인 경우 <math>\chi(G)\le 4</math> ([[사색정리]])