그래프 색칠: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
Osteologia (토론 | 기여) |
Osteologia (토론 | 기여) |
||
26번째 줄:
* <math>\omega(\Gamma)\le\chi(\Gamma)\le\Delta(\Gamma)+1</math>
여기서 <math>\omega(\Gamma)</math>는 <math>\Gamma</math>의 최대 [[클릭 (그래프 이론)|클릭]]의 크기이며, <math>\Delta(\Gamma)</math>는 <math>\Gamma</math>의 꼭짓점들의 차수들의 최댓값이다.
'''브룩스의 정리'''({{llang|en|Brooks’ theorem}})에 따르면, 임의의 연결 그래프 <math>\Gamma</math>에 대하여,
* <math>\chi(\Gamma)=\Delta(\Gamma)+1</math> * <math>\Gamma</math>는 [[완벽 그래프]]이거나 홀수 크기의 [[순환 그래프]]이다. * <math>\chi(G)\ge 3</math>
* <math>G</math>가 [[평면 그래프]]인 경우 <math>\chi(G)\le 4</math> ([[사색정리]])
* <math>G</math>가 [[평면 그래프]]이면서, 변 3개로 구성된 [[순환 (그래프 이론)|순환]]이 없는 경우 <math>\chi(G)\le 3</math> (그뢰치({{llang|de|Grötzsch}})의 정리)
| |||