비징의 정리

3. 성질

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

:$\backslash lim\_\{n\backslash to\backslash infty\}p(n)=1$

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

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

쾨니그의 정리에 따라, 모든 이분 그래프는 1종 그래프이다. Δ = 1일 때, 그래프는 스스로 매칭이 되어야 하며, 두 개의 모서리가 인접하지 않고, 에지 채색수는 1이다. Δ = 2일 때, 그래프는 경로와 사이클의 분리합집합이어야 한다. 모든 사이클이 짝수라면, 각 사이클 주위로 두 색상을 번갈아 사용함으로써 2-에지 채색이 가능하다. 그러나 적어도 하나의 홀수 사이클이 존재한다면, 2-에지 채색은 불가능하다.

3. 1. 에르되시-레니 모형

3. 2. 평면 그래프

3. 3. 이분 그래프

4. 증명

단순 무방향 그래프 를 생각하자. 여기서 은 에지의 개수이다. 이 정리는 그래프가 비어 있을 때 자명하게 성립한다. 이제 인 경우를 생각하고, 모든 에지 에 대해 가 적절한 -에지 채색을 갖는다고 가정한다.

색 }가 적절한 -에지 채색 에 대해 에서 누락되었다는 것은, 의 모든 이웃 에 대해 임을 의미한다. -경로는 에서 시작하여 색 에지를 갖고, 이후 에지 색상을 교대로 바꾸어 가는 (색, 색, 색, ...) 고유한 최대 경로이다. 이 경로의 길이는 0일 수도 있다. 가 의 적절한 -에지 채색이라면, 모든 정점은 에 대해 누락된 색을 가진다.

이제 가 적절한 -에지 채색을 갖지 않는다고 가정하자. 이는 다음과 동치이다.

:(1) 이고, 가 의 임의의 적절한 -에지 채색이며, 가 에서, 가 에서 에 대해 누락된 색일 때, 에서 시작하는 -경로는 에서 끝난다.

만약 (1)이 성립하지 않으면, -경로에서 와 색을 교환하고 의 색을 로 설정하여 로부터 의 적절한 -에지 채색을 얻을 수 있다. 반대로, 적절한 -에지 채색이 존재하면 를 제거하고 채색을 제한함으로써 (1)이 성립하지 않음을 보일 수 있다.

이제 이고, 이 의 적절한 -에지 채색이며, 가 에 대해 에서 누락되었다고 하자. 의 이웃들의 최대 수열 를 모든 에 대해 가 에 대해 에서 누락되도록 정의한다.

다음과 같이 채색 를 정의한다.

: (단, )

:는 정의되지 않음

:그 외의 경우,

그러면 의 정의에 의해 는 의 적절한 -에지 채색이 된다. 또한, 에 대해 에서 누락된 색은 에서도 동일하다.

를 에 대해 에서 누락된 색이라고 하자. 그러면 는 모든 에 대해 에 대해 에서도 누락된다. 는 에서 누락될 수 없다. 만약 그렇다면, 를 쉽게 확장할 수 있기 때문에, 모든 에 대해 에 색 에지가 인접하게 된다. 의 최대성에 의해, 가 되는 가 존재한다. 의 정의에 의해 다음이 성립한다.

:

를 에 대한 에서 시작하는 -경로라고 하자. (1)에 의해 는 에서 끝나야 한다. 하지만 는 에서 누락되었으므로, 는 색 에지로 끝나야 한다. 따라서 의 마지막 에지는 이다. 이제 를 에 대한 에서 시작하는 -경로라고 하자. 는 유일하게 결정되고, 의 내부 에지는 에서 변경되지 않으므로, 경로 는 와 동일한 에지를 반대 순서로 사용하고 를 방문한다. 로 이어지는 에지는 분명히 색이다. 하지만 는 에서 누락되었으므로, 는 에서 끝난다. 이는 (1)과 모순된다.

5. 그래프 분류

비징의 정리에 따라, 모든 그래프는 다음 두 종류로 분류된다.

• '''1종 그래프'''(class 1 graph^영어): 변 색칠수가 최대 차수와 같다.
• '''2종 그래프'''(class 2 graph^영어): 변 색칠수가 최대 차수보다 1 크다.

6. 비평면 곡면 위의 그래프

브란코 귄바움은 1969년에 토러스와 같은 임의의 2차원 유향 다양체에 다면체 임베딩을 갖는 모든 3-정규 그래프는 클래스 1에 속한다는 가설을 세웠다. 여기서 다면체 임베딩은 임베딩의 모든 면이 위상적으로 디스크이고 임베딩의 쌍대 그래프가 자기 루프 또는 다중 인접성이 없는 단순한 그래프 임베딩을 의미한다. 만약 이 가설이 참이라면, 이는 테이트에 의해 구에 다면체 임베딩을 갖는 3-정규 그래프가 클래스 1에 속한다는 명제와 동치임이 밝혀진 사색 정리의 일반화가 될 것이다. 하지만, Kochol|코촐^영어은 2009년에 고속 속성 가향 곡면에 다면체 임베딩을 갖는 스나크를 찾아 이 가설이 거짓임을 보였다.^[6] 이 구성을 바탕으로, 그는 다면체 임베딩된 그래프가 클래스 1에 속하는지 여부를 판단하는 문제는 NP-완전임을 또한 증명했다.^[6]

7. 알고리즘

미스라 & 그리즈 에지 채색 알고리즘는 그래프의 최대 차수에 대해 Δ + 1 색상으로 모든 그래프의 에지를 채색하는 다항 시간 알고리즘을 설명한다. 이 알고리즘은 클래스 2 그래프에 대해 최적의 색상 수를 사용하며, 모든 그래프에 대해 필요한 것보다 최대 하나의 색상을 더 사용한다. 이 알고리즘은 비징의 정리에 대한 원래 증명과 동일한 전략을 따른다. 즉, 채색되지 않은 그래프로 시작하여 채색된 에지 수를 1씩 증가시키기 위해 그래프를 다시 채색하는 방법을 반복적으로 찾는다.

더 구체적으로, 부분적으로 채색된 그래프에서 ''uv''가 채색되지 않은 에지라고 가정한다. 미스라와 그리즈의 알고리즘은 ''u''의 이웃에 대해 방향이 있는 의사 숲 ''P'' (각 정점이 최대 하나의 나가는 에지를 갖는 그래프)을 구성하는 것으로 해석할 수 있다. ''u''의 각 이웃 ''p''에 대해, 알고리즘은 ''p''에 인접한 에지 중 사용되지 않은 색상 ''c''를 찾고, 에지 ''uq''가 색상 ''c''를 갖는 정점 ''q'' (존재하는 경우)를 찾아 ''pq''를 ''P''에 에지로 추가한다. 두 가지 경우가 있다.

• 이 방식으로 구성된 의사 숲 ''P''가 ''v''에서 ''P''에서 나가는 에지가 없는 정점 ''w''까지의 경로를 포함하는 경우, ''u''와 ''w'' 모두에서 사용 가능한 색상 ''c''가 있다. 에지 ''uw''를 색상 ''c''로 다시 채색하면 나머지 에지 색상이 이 경로를 따라 한 단계씩 이동할 수 있다. 경로의 각 정점 ''p''에 대해, 에지 ''up''는 경로에서 ''p''의 후계자가 이전에 사용했던 색상을 사용한다. 이로 인해 에지 ''uv''를 포함하는 새로운 채색이 생성된다.
• 반면에, 의사 숲 ''P''에서 ''v''에서 시작하는 경로가 사이클로 이어지는 경우, ''w''를 경로가 사이클에 합류하는 ''u''의 이웃으로 하고, ''c''를 에지 ''uw''의 색상으로 하고, ''d''를 정점 ''u''의 모든 에지에서 사용되지 않은 색상으로 한다. 그런 다음 켐페 체인에서 색상 ''c''와 ''d''를 바꾸면 사이클이 끊어지거나 경로가 사이클에 합류하는 에지가 끊어져 이전 경우로 이어진다.

8. 역사

우크라이나의 수학자 바딤 게오르기예비치 비징(Вади́м Гео́ргиевич Визинг^ru, Вадим Георгійович Візінг|바딤 게오르기요비치 비징^uk)이 1964년에 이 정리를 증명하였다.^[11] 소련 수학자 바딤 비징이 노보시비르스크에서 연구하던 중 1964년에 발표하여 비징의 정리로 알려지게 되었다.^[2] 1965년부터 1967년까지 인도의 수학자 R. P. 굽타도 박사 과정을 밟으면서 독립적으로 이 정리를 발견했다.^[3][4] 비징은 자신의 연구가 멀티그래프를 최대 색상으로 채색할 수 있음을 보여주는 섀넌의 정리에 의해 동기 부여되었다고 언급했다. 비징의 정리는 현재 많은 그래프 이론 교과서에서 표준 자료가 되었지만, 처음에는 이 결과를 발표하는 데 어려움을 겪었고, 그의 논문은 잘 알려지지 않은 저널인 ''Diskret. Analiz''에 게재되었다.^[7]

참조

_[1] 학술지 A short proof for a generalization of Vizing's theorem Wiley Online Library 1991
_[2] harvtxt
_[3] 서적 Graph Edge Coloring: Vizing's Theorem and Goldberg's Conjecture https://books.google[...] John Wiley & Sons, Inc., Hoboken, NJ
_[4] 학술지 A brief history of edge-colorings – with personal reminiscences 2021-03-11
_[5] harvtxt
_[6] harvtxt
_[7] 문서
_[8] 인용 Note on the chromatic index of almost all graphs http://www.renyi.hu/[...] 1977
_[9] 저널 Критические графы с данным хроматическим классом 1965
_[10] 저널 Planar graphs of maximum degree seven are class I 2001
_[11] 저널 Об оценке хроматического класса ''p''-графа 1964