변 색칠

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

정의 
(단순) 그래프 의 변 색칠 은 다음 데이터로 구성된다.
 집합 
 함수 
이는 다음 조건을 만족시켜야 한다.
 서로 인접하는 두 변 에 대하여, 
변 색칠 에서, 의 원소를 색(色, )이라고 한다.

즉, 그래프 의 변 색칠은 그 선 그래프 의 그래프 색칠과 동치인 개념이다.

그래프가 가질 수 있는 변 색칠에서, 색의 수의 최솟값을 색칠 지표(色漆指標, )라고 하며, 로 쓴다. (이는 꼭짓점 색칠수 와 구분하기 위함이다.)

유일 k-변 색칠 그래프 
자연수 와 그래프 가 주어졌다고 하자. 만약  위의, 같은 색 집합 에 대한 임의의 두 변 색칠  및 에 대하여, 인 순열 이 항상 존재한다면, 를 유일 k-변 색칠 그래프()라고 한다.

성질 
비징의 정리(Визинг의定理, )에 따르면, 임의의 유한 그래프 에 대하여

이다. 여기서

는 의 꼭짓점의 차수의 최댓값이다.
이에 따라서, 모든 그래프는 다음과 같이 1종 그래프(一種graph, ) 및 2종 그래프(二種graph, )로 분류된다.
 1종 그래프의 경우 이다.
 2종 그래프의 경우 이다.
(이 정리는 다중 그래프에 대하여 성립하지 않는다.)

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

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

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

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

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

역사 
비징의 정리는 우크라이나의 수학자 바딤 게오르기예비치 비징(, )이 1964년에 증명하였다.

참고 문헌

외부 링크 
 
 
 
 
 
 
 
 

그래프 이론
그래프 색칠