변 색칠

그래프 이론에서 변 색칠(邊色漆, 영어: edge colo(u)ring은 그래프의 변들에, 같은 색이 인접하지 않도록 색을 부여하는 방법이다.^[1]^[2] 이를 사용하여 그래프의 불변량을 정의할 수 있다.

정의

(단순) 그래프 $G$ 의 변 색칠 $(C,c)$ 은 다음 데이터로 구성된다.

집합 $C$
함수 $c\colon \operatorname {E} (G)\to C$

이는 다음 조건을 만족시켜야 한다.

서로 인접하는 두 변 $e,e'\in \operatorname {E} (G)$ 에 대하여, $c(e)\neq c(e')$

변 색칠 $(C,c)$ 에서, $C$ 의 원소를 색(色, 영어: colo(u)r)이라고 한다.

즉, 그래프 $G$ 의 변 색칠은 그 선 그래프 $\operatorname {L} (G)$ 의 그래프 색칠과 동치인 개념이다.

그래프가 가질 수 있는 변 색칠에서, 색의 수의 최솟값을 색칠 지표(色漆指標, 영어: chromatic index)라고 하며, $\chi '(G)=\chi (\operatorname {L} (G))$ 로 쓴다. (이는 꼭짓점 색칠수 $\chi (G)$ 와 구분하기 위함이다.)

유일 k-변 색칠 그래프

자연수 $k$ 와 그래프 $G$ 가 주어졌다고 하자. 만약 $G$ 위의, 같은 색 집합 $C$ 에 대한 임의의 두 변 색칠 $(C,c)$ 및 $(C,c')$ 에 대하여, $c=\sigma \circ c'$ 인 순열 $\sigma \in \operatorname {Sym} (C)$ 이 항상 존재한다면, $G$ 를 유일 k-변 색칠 그래프(영어: uniquely $k$ -edge-colorable graph)라고 한다.

성질

비징의 정리(Визинг의定理, 영어: Vizing’s theorem)에 따르면, 임의의 유한 그래프 $G$ 에 대하여

\chi '(G)-\Delta (G)\in \{0,1\}

이다. 여기서

\Delta (G)=\max _{v\in \operatorname {V} (G)}\deg g\in \mathbb {N}

는 $G$ 의 꼭짓점의 차수의 최댓값이다. 이에 따라서, 모든 그래프는 다음과 같이 1종 그래프(一種graph, 영어: class 1 graph) 및 2종 그래프(二種graph, 영어: class 2 graph)로 분류된다.

1종 그래프의 경우 $\chi '(\Gamma )=\Delta (\Gamma )$ 이다.
2종 그래프의 경우 $\chi '(\Gamma )=\Delta (\Gamma )+1$ 이다.

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

유한 그래프의 색칠 지표가 주어진 자연수와 같은지 여부는 NP-완전 문제이다.

예

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

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

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

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

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

역사

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

각주

↑ Stiebitz, Michael; Scheide, Diego; Toft, Bjarne; Favrholdt, Lene M. (2012년 2월). 《Graph edge coloring: Vizing’s theorem and Goldberg’s conjecture》 (영어). Wiley. ISBN 978-1-118-09137-1.
↑ Fiorini, S.; Wilson, R. (1977). 《Edge-colourings of graphs》 (영어). Pittman.
↑ Визинг, В. Г. (1965). “Критические графы с данным хроматическим классом”. 《Дискретный Анализ》 (러시아어) 5: 9–17. Zbl 0171.44902.
↑ 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.
↑ 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
↑ Визинг, Вадим Георгиевич (1964). “Об оценке хроматического класса p-графа”. 《Дискретный Анализ》 (러시아어) 3: 25–30. MR 0180505.

외부 링크

“Vizing theorem”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4.
Weisstein, Eric Wolfgang. “Edge coloring”. 《Wolfram MathWorld》 (영어). Wolfram Research.
Weisstein, Eric Wolfgang. “Minimum edge coloring”. 《Wolfram MathWorld》 (영어). Wolfram Research.
Weisstein, Eric Wolfgang. “Edge chromatic number”. 《Wolfram MathWorld》 (영어). Wolfram Research.
Weisstein, Eric Wolfgang. “Vizing’s theorem”. 《Wolfram MathWorld》 (영어). Wolfram Research.
Weisstein, Eric Wolfgang. “Class 1 graph”. 《Wolfram MathWorld》 (영어). Wolfram Research.
Weisstein, Eric Wolfgang. “Class 2 graph”. 《Wolfram MathWorld》 (영어). Wolfram Research.
Beşeri, Tina (2004년 7월). “Edge coloring of a graph” (PDF) (영어). 석사 학위 논문. İzmir Yüksek Teknoloji Enstitüsü.

[1] Stiebitz, Michael; Scheide, Diego; Toft, Bjarne; Favrholdt, Lene M. (2012년 2월). 《Graph edge coloring: Vizing’s theorem and Goldberg’s conjecture》 (영어). Wiley. ISBN 978-1-118-09137-1.

[2] Fiorini, S.; Wilson, R. (1977). 《Edge-colourings of graphs》 (영어). Pittman.

[3] Визинг, В. Г. (1965). “Критические графы с данным хроматическим классом”. 《Дискретный Анализ》 (러시아어) 5: 9–17. Zbl 0171.44902.

[4] 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.

[5] 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

[6] Визинг, Вадим Георгиевич (1964). “Об оценке хроматического класса p-графа”. 《Дискретный Анализ》 (러시아어) 3: 25–30. MR 0180505.

[1]

[2]

[3]

[4]

[5]

[6]