변 색칠

위키백과, 우리 모두의 백과사전.
둘러보기로 가기 검색하러 가기
그래프의 3색 변 색칠
완전 그래프 의 7색 변 색칠

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

정의[편집]

(단순) 그래프 변 색칠 은 다음 데이터로 구성된다.

  • 집합
  • 함수

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

  • 서로 인접하는 두 변 에 대하여,

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

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

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

유일 k-변 색칠 그래프[편집]

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

성질[편집]

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

이다. 여기서

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

  • 1종 그래프의 경우 이다.
  • 2종 그래프의 경우 이다.

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

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

[편집]

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

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

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

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

역사[편집]

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

참고 문헌[편집]

  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. Zbl 1024.05031. doi:10.1006/jctb.2001.2047. 
  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. 

외부 링크[편집]