그래프 색칠: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
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>G</math>가 [[이분 그래프]]가 아니다).
| |||