변 색칠

3. 성질

(내용 없음)

3. 1. 비징의 정리

• '''1종 그래프''': 변 색칠수와 최대 차수가 같은 그래프 ($\backslash chi\text{'}(G)=\backslash Delta(G)$).
• '''2종 그래프''': 변 색칠수가 최대 차수보다 1 큰 그래프 ($\backslash chi\text{'}(G)=\backslash Delta(G)+1$).

4. 예

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

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

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

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

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

사이클 그래프는 사이클의 길이가 짝수일 경우 두 가지 색으로 변을 칠할 수 있다. 사이클을 따라 두 가지 색을 번갈아 사용하면 된다. 그러나 길이가 홀수인 경우에는 세 가지 색이 필요하다.^[1]

5. 응용

완전 그래프의 변 색칠은 라운드 로빈 토너먼트처럼 모든 참가자가 서로 한 번씩 경기를 치르는 리그의 일정을 짜는 데 유용하다. 그래프의 꼭짓점을 참가자로, 변을 경기로 생각하고, 각 변의 색깔을 경기가 열리는 라운드로 대응시키면 최소한의 라운드로 전체 경기 일정을 계획할 수 있다.^[25] 비슷한 방식으로, 내셔널 풋볼 리그(NFL)처럼 모든 팀이 서로 경기하지 않는 경우에도, 이전 시즌 성적 등을 바탕으로 결정된 경기 조합(그래프)에 변 색칠 알고리즘을 적용하여 시즌 경기 일정을 짤 수 있다.^[26] 비징의 정리에 따르면, 어떤 경기 조합이든 팀당 최대 경기 수보다 많아야 한 라운드(또는 주말)만 더 필요하게 일정을 계획할 수 있다.

오픈 샵 스케줄링은 여러 제품을 만들 때 각 제품마다 여러 공정(작업)을 거쳐야 하고, 각 공정은 특정 기계를 사용해야 하는 상황에서 생산 일정을 효율적으로 짜는 문제이다. 만약 모든 작업 시간이 같다면, 이 문제는 이분 그래프의 변 색칠 문제로 바꿀 수 있다. 그래프의 한쪽에는 제품, 다른 쪽에는 기계를 두고, 제품과 기계를 잇는 변은 해당 기계로 수행해야 할 작업을 나타낸다. 이때 변의 색깔은 작업을 수행할 시간 단계를 의미한다. 이분 그래프의 변 색칠은 다항 시간 내에 수행될 수 있으므로, 작업 시간이 동일하다는 제약 조건 하에서는 오픈 샵 스케줄링 문제도 효율적으로 풀 수 있다.^[27]

센서 네트워크에서 시분할 다중 접속(TDMA) 방식을 사용할 때, 각 센서 노드가 서로 간섭 없이 통신할 수 있도록 통신 시간대(타임 슬롯)를 할당하는 문제를 변 색칠을 응용하여 해결하려는 연구가 있다. 무선 통신 네트워크를 그래프로 보고, 각 통신 링크(변)에 시간대를 배정(색칠)하여 인접한 노드 간의 통신 간섭을 피하는 것이 목표이다. 강한 변 색칠(strong edge coloring)을 사용하면 해결 가능하지만, 필요 이상으로 많은 시간대가 필요할 수 있다. 대신, 각 통신 링크를 방향성을 가진 두 개의 변으로 간주하고, 특정 규칙에 따라 색칠(시간대 할당)하는 방식을 사용하기도 한다.

광섬유 통신에서는 여러 사용자(노드)가 동시에 통신할 때, 같은 광섬유 구간을 지나는 신호들이 서로 다른 주파수(색깔)를 사용하도록 경로와 주파수를 할당해야 한다. 이를 경로 색칠 문제라고 한다. 특히, 모든 노드가 중앙 스위치에 각각 연결된 스타 네트워크 구조에서는 이 문제를 변 색칠 문제로 정확히 모델링할 수 있다. 통신하는 노드를 그래프의 꼭짓점으로, 통신 요청(노드 쌍)을 변으로 보고, 사용 가능한 주파수를 색깔로 생각하면 된다. 즉, 같은 광섬유(중앙 스위치와 노드를 잇는 선)를 공유하는 통신 경로(변)들이 서로 다른 주파수(색깔)를 갖도록 하는 것이다.^[28] 더 복잡한 트리 구조 네트워크에서도 각 스위치를 중심으로 하는 스타 네트워크의 지역적인 경로 색칠 결과를 조합하여 전체 네트워크의 해답을 구할 수 있다.^[28]

6. 다른 유형

그래프의 Thue number는 모든 짝수 길이 경로에서 경로의 전반부와 후반부가 서로 다른 색상 순서를 가지도록 하는 더 강력한 요구 사항을 만족하는 변 색칠에 필요한 색상의 수이다.

그래프의 아보리티(arboricity)는 각 색상의 변들이 사이클을 형성하지 않도록 하는 데 필요한 최소 색상 수이다. 이는 표준 변 색칠 문제와 달리 인접한 변 쌍에 대한 제약이 없다. 즉, 그래프의 변들을 분할할 수 있는 숲의 최소 개수이다.^[19] 색칠 지수와 달리 그래프의 아보리티는 다항 시간 내에 계산할 수 있다.^[20]
리스트 변 색칠(list edge coloring)은 각 변에 허용되는 색상 목록이 주어졌을 때, 각 변의 색상을 해당 목록에서 선택하여 적절한 변 색칠을 찾는 문제이다. 그래프 ''G''의 리스트 색칠 지수는 각 변의 목록에 최소 ''k''개의 색상이 있다면, 목록이 어떻게 주어지든 항상 리스트 변 색칠이 가능한 가장 작은 수 ''k''이다. 따라서 리스트 색칠 지수는 항상 일반적인 색칠 지수보다 크거나 같다. 라틴 방진의 부분 완성과 관련된 Dinitz 추측은 완전 이분 그래프 ''K''_''n'',''n''의 리스트 변 색칠 수가 해당 변 색칠 수인 ''n''과 같다는 내용으로 해석될 수 있다. Galvin은 1995년에 더 나아가 모든 이분 그래프에서 색칠 지수와 리스트 색칠 지수가 같다는 것을 증명하여 이 추측을 해결했다. 자체 루프가 없는 임의의 다중 그래프에 대해서도 두 지수가 같다는 추측이 있지만, 이는 아직 해결되지 않았다.

꼭짓점 색칠에서 연구되는 여러 변형 개념들이 변 색칠에도 적용되었다.

• 완전 변 색칠(complete edge coloring): 완전 색칠의 변 색칠 버전으로, 모든 가능한 색상 쌍이 어떤 인접한 변 쌍에 나타나도록 하는 적절한 변 색칠이다. 목표는 사용된 총 색상 수를 최대화하는 것이다.
• 강한 변 색칠(strong edge coloring): 강한 색칠의 변 색칠 버전으로, 거리가 2 이하인(즉, 같은 꼭짓점에 인접하거나 인접한 꼭짓점들에 각각 인접한) 두 변이 서로 다른 색상을 가져야 하는 변 색칠이다.^[21] 강한 변 색칠은 무선 네트워크의 채널 할당 문제 등에 응용된다.
• 비순환 변 색칠(acyclic edge coloring): 비순환 색칠의 변 색칠 버전으로, 임의의 두 색상 클래스의 합집합이 비순환적인(즉, 숲을 이루는) 부분 그래프를 형성하는 적절한 변 색칠이다.^[22] 그래프 ''G''의 비순환 색칠 지수 ''a''′(''G'')는 ''G''가 적절한 비순환 변 색칠을 갖기 위한 최소 색상 수이다. ''a''′(''G'') ≤ Δ + 2 라는 추측이 있으며 (여기서 Δ는 ''G''의 최대 차수이다),^[23] 현재까지 알려진 가장 좋은 상한은 ''a''′(''G'') ≤ ⌈3.74(Δ − 1)⌉이다. 그래프의 둘레가 크면 문제가 더 쉬워진다. 구체적으로, 상수 ''c''가 존재하여 ''G''의 둘레가 최소 ''c''Δ log Δ이면 ''a''′(''G'') ≤ Δ + 2 가 성립한다. 또한, 임의의 ε > 0에 대해, ''G''의 둘레가 충분히 크면(어떤 ''g'' 이상이면) ''a''′(''G'') ≤ (1 + ε)Δ 가 성립한다.

7. 역사

비징의 정리는 우크라이나의 수학자 바딤 게오르기예비치 비징(Вади́м Гео́ргиевич Визинг^ru, Вадим Георгійович Візінг|바딤 게오르기요비치 비징^uk)이 1964년에 증명하였다.^[34] Misra와 Gries (1992), 그리고 Gabow, Nishizeki, Kariv, Leven (1985) 등은 비징의 정리에 의해 주어진 경계를 만족하는 모든 그래프를 $\backslash Delta\; +\; 1$개의 색상으로 칠하는 다항 시간 알고리즘을 설명했다. 관련 내용은 Misra & Gries edge coloring algorithm(미스라 & 그리즈 변 색칠 알고리즘)에서 찾아볼 수 있다.

다중 그래프의 경우, Karloff와 Shmoys (1987)는 Eli Upfal이 고안했다고 알려진 알고리즘을 제시했다. 이 알고리즘은 입력 다중 그래프 $G$에 홀수 차수 정점마다 새로운 정점을 추가하여 오일러 경로를 만들 수 있도록 변형한다. 오일러 경로를 찾고 경로의 방향을 정한 뒤, 이분 그래프 $H$를 만든다. 이분 그래프 $H$의 양쪽에는 $G$의 각 정점에 해당하는 두 개의 복사본이 있으며, $G$에서 $u$에서 $v$로 가는 방향성 경로가 있다면, $H$의 왼쪽 $u$ 정점에서 오른쪽 $v$ 정점으로 가는 변이 존재한다. 이분 그래프 $H$에 변 색칠 알고리즘을 적용한다. $H$의 각 색상 종류는 $G$의 변 집합에 해당하며, 이는 최대 차수가 2인 부분 그래프, 즉 경로와 순환의 분리된 합집합을 형성한다. 따라서 $H$의 각 색상 종류에 대해 $G$에서 세 개의 색상 종류를 형성할 수 있다. 이 알고리즘의 시간 복잡도는 이분 그래프 변 색칠 시간에 의해 결정되며, Cole, Ost, Schirra (2001)의 알고리즘을 사용하면 $O(m\; \backslash log\; \backslash Delta)$이다. 이 알고리즘이 사용하는 색상의 수는 최대 $3\; \backslash lceil\; \backslash frac\{\backslash Delta\}\{2\}\; \backslash rceil$개로, Shannon의 경계인 $\backslash lfloor\; \backslash frac\{3\backslash Delta\}\{2\}\; \backslash rfloor$와 거의 같지만 완전히 일치하지는 않는다. 이 알고리즘은 병렬 알고리즘으로 쉽게 변환될 수 있다. 같은 논문에서 Karloff와 Shmoys는 최대 차수가 3인 다중 그래프를 4가지 색상으로 칠하는 선형 시간 알고리즘도 제시했다. 이 알고리즘은 Shannon과 Vizing의 경계 모두를 만족하며 비슷한 원리로 작동한다. 즉, 그래프를 오일러 경로가 가능하도록 새 정점을 추가하고, 오일러 경로를 찾은 다음, 경로에서 변의 교대 집합을 선택하여 그래프를 최대 차수가 2인 두 개의 부분 그래프로 나눈다. 각 부분 그래프의 경로와 짝수 순환은 각 부분 그래프당 두 가지 색상으로 칠할 수 있다. 이후 남은 홀수 순환은 반대쪽 부분 그래프에 속한 두 색상 중 하나로 칠할 수 있는 변을 최소 하나 이상 포함하게 된다. 이 변을 홀수 순환에서 제거하면 경로가 남게 되고, 이 경로는 해당 부분 그래프의 두 가지 색상을 사용하여 칠할 수 있다.

그래프나 다중 그래프의 변을 하나씩 고려하며 각 변에 사용 가능한 첫 번째 색상을 할당하는 탐욕적 색칠 알고리즘은 때로는 최대 $2\backslash Delta\; -\; 1$개의 색상을 사용할 수 있다. 이는 필요한 색상 수의 거의 두 배에 달할 수 있다. 그러나 이 알고리즘은 입력 그래프를 미리 알 수 없는 온라인 알고리즘 환경에서 유용하다는 장점이 있다. 이러한 환경에서 알고리즘의 경쟁 비율은 2이며, 이는 최적이다. 즉, 다른 어떤 온라인 알고리즘도 이보다 더 나은 성능을 달성할 수 없다.^[11] 하지만 변들이 무작위 순서로 도착하고 입력 그래프의 차수가 로그 함수 이상으로 크다면 더 작은 경쟁 비율을 달성할 수도 있다.^[12]

여러 연구자들은 어떤 다중 그래프의 분수 색상 지수(선형 계획법을 사용하여 다항 시간 내에 계산 가능)가 실제 색상 지수와 1 이내의 차이를 가질 것이라는 추측을 제기했다.^[13] 만약 이 추측이 사실이라면, 다중 그래프의 경우 실제 색상 지수와 최대 1만큼 차이 나는 값을 계산할 수 있게 되며, 이는 단순 그래프에 대해 비징의 정리를 통해 알려진 사실과 유사하다. 이 추측이 일반적으로 증명되지는 않았지만, 색상 지수가 $\backslash Delta\; +\; \backslash sqrt\{\backslash Delta/2\}$ 이상일 때, 즉 충분히 큰 중복도를 가진 다중 그래프의 경우에는 성립하는 것으로 알려져 있다.^[14]

8. 미해결 문제

Jensen과 Toft는 1995년에 변 색칠에 관한 23개의 미해결 문제를 나열했으며, 그중 일부는 다음과 같다.

• Goldberg (1973)의 추측: 색 지수와 분수 지수는 서로 1 이내의 값을 가지며, 이를 통해 색 지수를 다항 시간 내에 한 가지 색상 차이 내로 근사할 수 있다는 추측이다.
• Jakobsen 등의 추측: 최대 차수가 더 작거나 클래스 1인 임의의 부분 그래프를 갖는 클래스 2 그래프인 변 색칠에 대한 임계 그래프 구조에 관한 여러 추측이다. Jakobsen은 원래 모든 임계 그래프가 홀수 개의 정점을 갖는다고 추측했으나, 이는 나중에 반증되었다. 이 추측을 약화시키거나 임계 그래프 및 임계 멀티그래프의 정점 수를 제한하는 몇 가지 다른 추측은 여전히 미해결 상태이다.
• Vizing의 문제: 클래스 2 평면 그래프가 가질 수 있는 최대 차수를 분류하는 문제이다.
• A. J. W. Hilton의 과포화 부분 그래프 추측: 차수가 최소 ''n''/3인 그래프는 클래스 1이거나, 원래 그래프와 동일한 차수 Δ를 갖고 정점 수가 홀수 ''k''개이며 부분 그래프의 변 수가 Δ(''k'' - 1)/2보다 큰 부분 그래프를 포함한다는 추측이다. 또한, 높은 차수 그래프 대신 평면 그래프에 대한 헤르베르트 그뢰치와 폴 시모어의 유사한 추측도 있다.
• Amanda Chetwynd와 Anthony Hilton의 추측 (아마도 Gabriel Andrew Dirac의 연구에서 비롯됨): 짝수 개의 정점 ''n''을 갖고 차수가 최소 ''n''/2인 정규 그래프는 클래스 1이라는 추측이다.
• 클로드 베르주와 D. R. 풀커슨의 추측: 단절선이 없는 3-정규 단순 그래프의 모든 변을 두 배로 늘려 형성된 6-정규 멀티그래프는 여섯 가지 색상으로 변 색칠될 수 있다는 추측이다.
• Fiorini와 Wilson의 추측: 갈고리 그래프 ''K''_1,3를 제외한 모든 삼각형 없는 그래프는 유일하게 3-변 색칠 가능하지 않다는 추측이다.
• 2012년 추측: ''d''-정규 평면 멀티그래프 ''G''가 ''d''-변 색칠 가능할 필요충분조건은 ''G''가 홀수 ''d''-변 연결되어 있다는 추측이다. 이 추측은 ''d''=3일 때의 네 색상 정리를 일반화한 것이다. 마리아 추드노브스키, Katherine Edwards, 그리고 폴 시모어는 8-정규 평면 멀티그래프는 변 색 지수 8을 갖는다는 것을 증명했다.

참조

_[1] harvtxt
_[2] harvtxt
_[3] harvtxt
_[4] harvtxt
_[5] harvtxt
_[6] harvtxt
_[7] harvtxt
_[8] harvtxt
_[9] harvtxt
_[10] harvtxt
_[11] harvtxt
_[12] harvtxt
_[13] harvtxt
_[14] harvtxt
_[15] harvtxt
_[16] harvtxt
_[17] harvtxt
_[18] harvtxt
_[19] harvtxt
_[20] harvtxt
_[21] harvtxt
_[22] harvtxt
_[23] harvtxt
_[24] harvtxt
_[25] harvtxt
_[26] harvtxt
_[27] harvtxt
_[28] harvtxt
_[29] 서적 Graph edge coloring: Vizing’s theorem and Goldberg’s conjecture http://www.wiley.com[...] Wiley 2012-02
_[30] 서적 Edge-colourings of graphs Pittman 1977
_[31] 저널 Критические графы с данным хроматическим классом 1965
_[32] 저널 Planar graphs of maximum degree seven are class I 2001
_[33] 인용 Note on the chromatic index of almost all graphs http://www.renyi.hu/[...] 1977
_[34] 저널 Об оценке хроматического класса ''p''-графа 1964