비징의 정리

그래프 이론에서, Vizing의 정리는 모든 단순 비방향 그래프는 그래프의 최대 Δ보다 최대 1개 큰 색상을 사용하여 에지 색상으로 칠할 수 있다고 명시한다.적어도 Δ 색상은 항상 필요하므로 Δ 색상이 충분한 "클래스 1" 그래프와 Δ + 1 색상이 필요한 "클래스 2" 그래프 두 종류로 분할할 수 있다.보다 일반적인 버전의 Vizing의 정리에서는 루프가 없는 모든 비방향 다중 글램은 최대 Δ+µ 색상으로 색칠할 수 있다고 명시하고 있으며, 여기서 µ는 다중 글램의 다중성이다.이 정리는 1964년에 그것을 출판한 바딤 G. 비징의 이름을 따서 명명되었다.

예

Δ = 1일 때 그래프 G는 두 가장자리가 인접하지 않은 일치해야 하며 가장자리 색도 숫자는 1이어야 한다.즉, Δ(G) = 1인 모든 그래프는 1등급이다.

Δ = 2일 때 그래프 G는 경로와 주기의 분리된 결합이어야 한다.모든 사이클이 짝수일 경우, 각 사이클을 중심으로 두 색상을 번갈아 가면서 2엣지 색상을 만들 수 있다.그러나 적어도 하나의 홀수 사이클이 존재한다면 2-엣지 컬링은 불가능하다.즉, Δ = 2가 있는 그래프는 초당적인 경우에만 1등급이다.

증명

이 증거는 디에스텔(2000년)에서 영감을 얻은 것이다.

G = (V, E)를 단순 비방향 그래프로 한다.우리는 가장자리 수인 m에 유도하여 진행한다.그래프가 비어 있으면 그 정리가 대수롭지 않게 유지된다.m > 0으로 하고 모든 G - xy에 대해 적절한 (Δ+1)-엣지 색상이 존재한다고 가정한다(xy ∈ E).

우리는 모든 y ) N(x)에 대해 c(xy) α인 경우 적절한 (Δ+1)-엣지컬링 c에 관하여 x ∈ V에서 색 α α α α α가 누락되었다고 말한다.또한 x의 α/β-경로는 α색 가장자리로 x에서 시작하여 에지의 색상을 교대로 하는 고유한 최대 경로를 나타내도록 한다(두 번째 가장자리는 색상 β, 세 번째 가장자리는 색상 α 등을 가지며), 길이는 0이 될 수 있다.c가 G의 적절한 (Δ+1) 에지 색상인 경우, 모든 꼭지점에는 c에 대한 색상이 누락된다는 점에 유의하십시오.

G의 적절한 Δ+1) 에지 색상이 존재하지 않는다고 가정한다.이는 다음과 같은 진술과 동일하다.

(1) xy ∈ E 및 c는 임의적 적정(Δ+1)으로 한다. G - xy 및 α의 엣지컬링은 x에서 누락되고 β는 c에서 누락된다.그런 다음 y에서 α/β- 경로가 x로 끝난다.

(1)이 지탱하지 못하면 α/β 경로에 있는 α와 β를 서로 바꾸어 xy의 색상을 α로 설정하여 c에서 G의 적절한 (Δ+1) 에지 색상을 만들 수 있기 때문에 이것은 동등하다.반대로 적절한 (Δ+1) 에지 색상이 존재한다면, xy를 삭제하고 색상을 제한하면 (1)도 지탱하지 못할 것이다.

이제 xy₀ ∈ E와 c를₀ 적절한 (Δ+1)-에지 색상 G - xy와₀ α가 c에₀ 대해 x에서 누락되도록 한다.우리는 y₀, ...y를_k 모든 0 < i ≤ k에 대해₀ c₀(xy_i)가 y에서_i−1 누락되는 x의 최대 이웃 시퀀스로 정의한다.

우리는₁ c, ...,c를_k 다음과 같이 정의한다.

c_i(xy_j)=c₀(xy_j+1)는 모두 0 ≤ j < i,

c_i(xy_i)가 정의되지 않음,

그렇지_i0 않으면

그 다음 c는_i0 y, ...,y의_k 정의로 인해 G - xy의_i 적절한 (Δ+1) 에지 색상이 된다. 또한 x의 누락된 색상은 모든 0 ≤ i k k에 대해 c와_i 동일하다는 점에 유의한다.

β를 c에₀ 관해서 y에서_k 누락된 색으로 두십시오. 그러면 β는 모든 0 i i k k에서 c에_i 관해서도 y에서_k 누락된다.β는 x에서 누락될 수 없다는 점에 유의하십시오. 그렇지_k 않으면 c를 쉽게 확장할 수 있으며, 따라서 β를 가진 가장자리는 모든 c에서_j x에 입사할 수 있다.k의 최대성으로부터, c₀(xy_i) = β와 같은 1 i i < k가 존재한다. c₁, ...,c의 정의로부터_k, 이것은 다음을 지탱한다.

c₀(xy_i) = c_i−1(xy_i) = c_k(xy_i−1) = β

c에_k 관해서 P를 y로부터_k α/β-경로가 되게 한다.(1)부터 P는 x로 끝나야 한다. 그러나 α는 x에서 빠져 있으므로 색상 β의 가장자리로 끝나야 한다.따라서 P의 마지막 가장자리는 yx이다_i−1.이제, C에 관해서_i−1 P는 y로부터_i−1 α/β- 경로가 되게 한다.p₀'는 c,...,c에서_k P의 내측 가장자리가 고유하게 결정되고 변경되지 않기 때문에 경로 P'는 역순으로 P와 동일한 가장자리를 사용하고_k y를 방문한다.y로_k 이어지는 가장자리에는 분명히 색 α가 있다.그러나 β는 y에서_k 빠져 있으므로 p'는 y로_k 끝난다.그것은 위의 (1)과 모순되는 것이다.

그래프 분류

몇몇 저자들은 일부 그래프를 클래스 1 또는 클래스 2로 분류하는 추가 조건을 제공했지만 완전한 분류는 제공하지 않았다.예를 들어, 그래프 G의 최대 Δ의 정점이 독립된 집합을 형성하거나, 이 정점 집합에 대해 유도된 하위 그래프가 숲인 경우 보다 일반적으로 G는 등급 1이어야 한다.^[1]

Erdows & Wilson(1977)은 거의 모든 그래프가 1등급이라는 것을 보여주었다.즉, 모든 n-vertex 그래프가 동일한 확률의 무작위 그래프의 Erdss-Rény 모델에서 p(n)가 이 분포에서 도출된 n-vertex 그래프가 1등급일 확률을 갖도록 한 다음, p(n)가 n이 무한대로 이동할 때 한계에 1에 접근한다.p(n)가 하나로 수렴되는 속도에 대한 보다 정확한 한계는 Frieze 외 연구진(1988)을 참조한다.

평면 그래프

Vizing(1965)은 평면 그래프의 최대도가 8 이상일 경우 1등급임을 보여주었다.이와는 대조적으로, 그는 2-5 범위의 최대 도에 대해 2등급의 평면 그래프가 존재한다고 관찰했다.2도에서는 모든 홀수 사이클이 그러한 그래프이며, 3도, 4도, 5도에서는 이러한 그래프를 인접한 두 가장자리의 경로로 단일 가장자리를 대체하여 플라토닉 고형물로 구성할 수 있다.

Vizing의 평면 그래프 추측에서 Vizing(1965)은 최대 도 6 또는 7을 가진 모든 단순 평면 그래프는 1등급이며 나머지 가능한 사례를 종결한다고 명시한다.독립적으로, 장(2000년)과 샌더스 & 자오(2001년)는 최고도 7을 가진 모든 평면 그래프가 1등급이라는 것을 보여주면서 바이징의 평면 그래프 추측을 부분적으로 증명했다.따라서 미해결로 남아 있는 추측의 유일한 경우는 최대 6도 정도밖에 되지 않는다.이 추측은 총체적인 색채 추측에 영향을 미친다.

플라톤 고형물의 분할에 의해 구성된 등급 2의 평면 그래프는 정규적이지 않다. 즉, 등급 2의 정점과 높은 정점이 있다.평면 그래프의 정점 색상에 대한 4가지 색상 정리(1976년 Appel & Haken에 의해 증명됨)는 모든 브리지리스 3-정규 평면 그래프가 1등급(Tait 1880)이라는 문구와 동등하다.

평면이 아닌 표면의 그래프

1969년 브란코 그룬바움(Branko Grünbaum)은 토러스 같은 2차원 지향 다지관에 다면체가 내장되어 있는 모든 3개의 정규 그래프는 1등급이어야 한다고 추측했다.이 맥락에서 다면 임베딩은 임베딩의 모든 면이 토폴로지적으로 디스크로 되어 있고 임베딩의 이중 그래프가 단순하여 자체 루프나 다중 보조가 없는 그래프를 내장한 그래프다.만일 사실이라면 이것은 4색 정리를 일반화한 것으로서, 타이트에 의해 구체에 다면체를 내장한 3개의 정규 그래프가 1등급이라는 진술과 동등한 것으로 나타났다.그러나 코철(2009)은 다면체 임베딩이 있는 스네이크를 고천성 오리엔탈 표면에 발견해 추측이 거짓임을 보여줬다.그는 이 구성을 바탕으로 다면체 내장 그래프가 1등급인지 여부를 확인하는 것이 NP 완성도라는 점도 보여줬다.^[2]

알고리즘

Misra & Gries(1992)는 그래프의 가장자리를 Δ + 1 색상으로 염색하기 위한 다항 시간 알고리즘을 설명한다. 여기서 Δ는 그래프의 최대 수준이다.즉, 알고리즘은 2등급 그래프에 최적의 색상 수를 사용하고, 모든 그래프에 필요한 색상보다 최대 한 가지 색상을 더 사용한다.그들의 알고리즘은 바이징이 그의 정리를 증명하는 원래 전략과 같은 전략을 따른다: 그것은 무색화 그래프에서 시작하여 색칠된 가장자리 수를 한 개씩 늘리기 위해 그래프를 회상하는 방법을 반복적으로 찾는다.

구체적으로는 부분적인 색상의 그래프에서 uv가 무색상의 가장자리라고 가정해 보자.Misra와 Gries의 알고리즘은 u의 이웃에 지시된 사이비 포리스트 P(각 정점이 최대 하나의 나가는 가장자리가 있는 그래프)를 구성하는 것으로 해석할 수 있다: u의 각 이웃 p에 대해 알고리즘은 p에 입사하는 가장자리 중 어느 하나에서 사용되지 않는 색 c를 찾아내고, uq가 색상을 갖는 정점 q(있는 경우)를 찾아낸다., 그리고 P에 가장자리로서 pq를 추가한다.두 가지 경우가 있다.

• 이런 식으로 구성된 사이비포리스트 P가 p에 발신 에지가 없는 v에서 정점 w까지의 경로를 포함하고 있다면 u와 w 모두에서 사용할 수 있는 c 색상이 있다.c 컬러로 기억되는 에지 uw는 이 경로를 따라 나머지 에지 색상을 한 단계 이동시킬 수 있다: 경로의 각 꼭지점 p에 대해 에지 업은 경로의 p 후속자가 이전에 사용했던 색상을 취한다.이것은 가장자리 UV를 포함하는 새로운 색상으로 이어진다.
• 반면 사이비숲 P에서 v에서 시작하는 경로가 사이클로 이어지면 w는 사이클과 결합하는 u의 이웃으로, c는 엣지 uw의 색으로, d는 꼭지 u의 어떤 가장자리에서도 사용되지 않는 색으로 한다.그런 다음 켐페 체인의 색상 c와 d를 교환하면 경로가 사이클과 결합하는 사이클이나 가장자리가 깨져 이전 사례로 이어진다.

각 꼭지점에서 사용되고 사용할 수 있는 색상을 추적하기 위한 간단한 데이터 구조로 P의 구성과 알고리즘의 기억 단계는 모두 시간 O(n)로 구현할 수 있으며, 여기서 n은 입력 그래프의 정점 수입니다.이 단계들은 m를 반복해야 하기 때문에, 각각의 반복이 컬러 에지의 수를 1씩 증가시키므로, 총 시간은 O(mn)이다.

가보우 외 연구진(1985)은 미발표 기술 보고서에서 Δ+1 색상으로 색칠하는 동일한 문제에 대해 더 빠른 $O{\displaystyle (m}$ n ${\displaystyle \log }$ ${\displaystyle n}$ $){\$sqrt{n}\$displaystyle O(m{\sqrt{n}\log$ n$)}$ 시간을$$ 주장했다.

역사

구틴 & 토프트(2000년)와 소이퍼(2008년) 두 가지에서 바이징은 그의 작품이 섀넌(1949년)의 정리에서 동기 부여된 것이라고 언급하고 있는데, 이는 멀티그램이 최대 (3/2)Δ의 색으로 채색될 수 있다는 것을 보여준다.비록 바이징의 정리가 현재 많은 그래프 이론 교과서에 표준 자료가 되고 있지만, 바이징은 처음에 그 결과를 발표하는데 어려움을 겪었고, 그것에 대한 그의 논문은 무명의 저널인 디스켓에 나온다. 아놀리즈.^[3]

참고 항목

• 최대 정점 색상과 관련된 Brooks의 정리

메모들

참조

• Appel, K.; Haken, W. (1976), "Every planar map is four colorable", Bulletin of the American Mathematical Society, 82 (5): 711–712, doi:10.1090/S0002-9904-1976-14122-5, MR 0424602.
• Diestel, Reinhard (2000), Graph Theory (PDF), Berlin, New York: Springer-Verlag, pp. 103–104.
• Erdős, Paul; Wilson, Robin J. (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.
• Fournier, Jean-Claude (1973), "Colorations des arêtes d'un graphe", Cahiers du Centre d'Études de Recherche Opérationnelle, 15: 311–314, MR 0349458.
• Frieze, Alan M.; Jackson, B.; McDiarmid, C. J. H.; Reed, B. (1988), "Edge-colouring random graphs", Journal of Combinatorial Theory, Series B, 45 (2): 135–149, doi:10.1016/0095-8956(88)90065-2, MR 0961145.
• Gabow, Harold N.; Nishizeki, Takao; Kariv, Oded; Leven, Daniel; Terada, Osamu (1985), Algorithms for edge-coloring graphs, Tech. Report TRECIS-8501, Tohoku University.
• Gutin, Gregory; Toft, Bjarne (December 2000), "Interview with Vadim G. Vizing" (PDF), European Mathematical Society Newsletter, 38: 22–23.
• Kochol, Martin (2009), "Polyhedral embeddings of snarks in orientable surfaces", Proceedings of the American Mathematical Society, vol. 137, pp. 1613–1619.
• Kochol, Martin (2010), "Complexity of 3-edge-coloring in the class of cubic graphs with a polyhedral embedding in an orientable surface", Discrete Applied Mathematics, 158 (16): 1856–1860, doi:10.1016/j.dam.2010.06.019, MR 2679785.
• Misra, J.; Gries, David (1992), "A constructive proof of Vizing's Theorem", Information Processing Letters, 41 (3): 131–133, doi:10.1016/0020-0190(92)90041-S.
• Sanders, Daniel P.; Zhao, Yue (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.
• Shannon, Claude E. (1949), "A theorem on coloring the lines of a network", J. Math. Physics, 28: 148–151, MR 0030203.
• Soifer, Alexander (2008), The Mathematical Coloring Book, Springer-Verlag, pp. 136–137, ISBN 978-0-387-74640-1.
• Tait, P. G. (1880), "Remarks on the colourings of maps", Proc. R. Soc. Edinburgh, 10: 729.
• Vizing, V. G. (1964), "On an estimate of the chromatic class of a p-graph", Diskret. Analiz., 3: 25–30, MR 0180505.
• Vizing, V. G. (1965), "Critical graphs with given chromatic class", Metody Diskret. Analiz., 5: 9–17. (러시아어로)
• Zhang, Limin (2000), "Every planar graph with maximum degree 7 is of class 1", Graphs and Combinatorics, 16 (4): 467–495.

외부 링크

• 플래닛매트릭스에서 바이징의 정리 증명.