비징의 정리

그래프 이론에서, 비징의 정리(Визинг의定理, 영어: Vizing’s theorem)는 그래프변 색칠수와 최대 차수의 차가 0 또는 1이라는 정리다. 이를 통해 모든 그래프를 두 종류로 분류할 수 있다.

정의편집

비징의 정리에 따르면, (단순 무향) 그래프  의 변 색칠수   의 최대 차수

 

사이에 다음과 같은 관계가 성립한다.

 

이에 따라서, 모든 그래프는 다음과 같이 1종 그래프(영어: class 1 graph) 및 2종 그래프(영어: class 2 graph)로 분류된다.

  • 1종 그래프의 경우  이다.
  • 2종 그래프의 경우  이다.

이 정리는 다중 그래프에 대하여 성립하지 않는다.

성질편집

에르되시-레니 모형(영어: Erdős–Rényi model)에서,  개의 꼭짓점을 갖는 무작위 그래프가 1종 그래프일 확률  은 다음과 같은 극한을 갖는다.[1]

 

즉, 에르되시-레니 모형에서 거의 모든 그래프는 1종 그래프이다.

최대 차수가 7 이상인 평면 그래프는 1종 그래프이다. 이 정리는 최대 차수가 8 이상인 경우는 비징이 증명하였고,[2] 7인 경우는 2001년에 증명되었다.[3] 최대 차수가 5 이하인 경우, 2종 평면 그래프가 존재하며, 이러한 그래프들은 정다면체로부터 작도할 수 있다. 최대 차수가 6인 경우는 미해결 문제로 남아 있다.

쾨니그의 정리에 따라, 모든 이분 그래프는 1종 그래프이다.

역사편집

우크라이나의 수학자 바딤 게오르기예비치 비징(러시아어: Вади́м Гео́ргиевич Визинг, 우크라이나어: Вадим Георгійович Візінг 바딤 게오르기요비치 비징[*])이 1964년에 증명하였다.[4]

참고 문헌편집

  1. Erdős, Paul; Robin J. Wilson (1977), “Note on the chromatic index of almost all graphs” (PDF), 《Journal of Combinatorial Theory (Series B)》 (영어) 23 (2–3): 255–257, doi:10.1016/0095-8956(77)90039-9 
  2. Визинг, В. Г. (1965). “Критические графы с данным хроматическим классом”. 《Дискретный Анализ》 (러시아어) 5: 9–17. Zbl 0171.44902. 
  3. Sanders, Daniel P.; Yue Zhao (2001). “Planar graphs of maximum degree seven are class I”. 《Journal of Combinatorial Theory (Series B)》 (영어) 83 (2): 201–212. doi:10.1006/jctb.2001.2047. Zbl 1024.05031. 
  4. Визинг, В. Г. (1964). “Об оценке хроматического класса p-графа”. 《Дискретный Анализ》 (러시아어) 3: 25–30. MR 0180505. 

외부 링크편집