변 색칠

파일:Desargues graph 3color edge.svg

그래프의 3색 변 색칠

섬네일을 만드는 중 오류 발생:

완전 그래프 $K_8$의 7색 변 색칠

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

정의

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

• 집합 $C$
• 함수 $c:\mathrm{E}(G)\to C$

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

• 서로 인접하는 두 변 $e,e^{\prime }\in \mathrm{E}(G)$에 대하여, $c(e)\ne c(e^{\prime })$

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

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

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

유일 k-변 색칠 그래프

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

성질

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

${\chi }^{\prime }(G)-\Delta (G)\in \{0,1\}$

이다. 여기서

$\Delta (G)=\underset{v\in \mathrm{V}(G)}{\max }\mathrm{deg}g\in \mathbb{N}$

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

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

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

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

예

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

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

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

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

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

역사

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

외부 링크

• “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ü.