비징의 정리

틀:위키데이터 속성 추적 그래프 이론에서 비징의 정리(Визинг의定理, 틀:Llang)는 그래프의 변 색칠수와 최대 차수의 차가 0 또는 1이라는 정리다. 이를 통해 모든 그래프를 두 종류로 분류할 수 있다.

정의

비징의 정리에 따르면, (단순 무향) 그래프 $\mathrm{\Gamma }$의 변 색칠수 ${\chi }^{\prime }(\mathrm{\Gamma })$ 및 $\mathrm{\Gamma }$의 최대 차수

$\mathrm{\Delta }(\mathrm{\Gamma })=\underset{v\in V(\mathrm{\Gamma })}{\max }\mathrm{\Delta }(v)$

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

$\mathrm{\Delta }(\mathrm{\Gamma })\le {\chi }^{\prime }(\mathrm{\Gamma })\le \mathrm{\Delta }(\mathrm{\Gamma })+1$

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

• 1종 그래프의 경우 ${\chi }^{\prime }(\mathrm{\Gamma })=\mathrm{\Delta }(\mathrm{\Gamma })$이다.
• 2종 그래프의 경우 ${\chi }^{\prime }(\mathrm{\Gamma })=\mathrm{\Delta }(\mathrm{\Gamma })+1$이다.

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

성질

에르되시-레니 모형(틀:Llang)에서, $n$개의 꼭짓점을 갖는 무작위 그래프가 1종 그래프일 확률 $p(n)$은 다음과 같은 극한을 갖는다.

$\underset{n\to \mathrm{\infty }}{\lim }p(n)=1$

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

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

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

역사

우크라이나의 수학자 바딤 게오르기예비치 비징(틀:Llang, 틀:Llang)이 1964년에 증명하였다.

외부 링크

• 틀:Eom