(일부 용어 출처: http://mathsci.kaist.ac.kr/~sangil/ko/2015/%EA%B7%B8%EB%9E%98%ED%94%84-%EC%9D%B4%EB%A1%A0-%EC%9A%A9%EC%96%B4-%EC%9A%B0%EB%A6%AC%EB%A7%90-%EB%B2%88%EC%97%AD/) 태그: 분류가 필요합니다! |
잔글편집 요약 없음 태그: 모니위키(나무위키) 문법 사용이 의심됨 |
||
| 12번째 줄: | 12번째 줄: | ||
* <math>K</math>는 안정하다. 즉, 어느 두 꼭짓점도 인접해 있지 않다. | * <math>K</math>는 안정하다. 즉, 어느 두 꼭짓점도 인접해 있지 않다. | ||
* 모든 <math>K</math>에 있지 않은 꼭짓점 <math>u \in V(D') \setminus K</math>에 대하여, <math>u</math>에서 <math>K</math>로의 변이 존재한다. | * 모든 <math>K</math>에 있지 않은 꼭짓점 <math>u \in V(D') \setminus K</math>에 대하여, <math>u</math>에서 <math>K</math>로의 변이 존재한다. | ||
=== 보조정리의 증명 === | |||
<math>|V(D)|</math>에 대한 귀납법으로 증명한다. <math>|V(D)|</math>가 최소인 경우는 1일 때이고, 이때는 자명하다. 리스트 배정에 쓰인 색 <math>\displaystyle\alpha \in \bigcup_{v\in V(D)} L(v) </math>을 택하여, 다음과 같은 유도 부분그래프를 만들자: | |||
:<math>D' = D\left[ \left\{v \in V(D):~~ \alpha \in L(v)\right\} \right]</math> | |||
<math>K</math>를 <math>D'</math>의 핵이라고 하면, <math>K</math>는 안정하므로 모든 <math>K</math>의 꼭짓점을 <math>\alpha</math>로 칠할 수 있다. 이제 <math>D'' = D \setminus K</math>라고 하면, 핵의 성질에 의해 <math>\operatorname{deg}_D^+(v) \ge \operatorname{deg}_{D''}^+ + 1</math>이므로 | |||
:<math>|L(v) \setminus \{\alpha\}| \ge \operatorname{deg}_{D''}^+ + 1</math> | |||
이다. 귀납법의 가정에 의하여 <math>D''</math>는 <math>\alpha</math>를 사용하지 않는 <math>L</math>-리스트 채색이 가능하고, 따라서 <math>D</math> 역시 <math>L</math>-리스트 채색이 가능하게 된다. | |||
=== 갈빈의 이분 리스트 변 채색 정리의 증명 === | |||
2017년 11월 12일 (일) 15:08 판
갈빈의 이분 리스트 변 채색 정리(Galvin's bipartite list-edge-coloring theorem)은 프레드 갈빈(Fred Galvin)이 디니츠 추측을 일반화하여 해결하면서 만들어진 정리이다.
진술
임의의 이분 (다중) 그래프 [math]\displaystyle{ G }[/math]에 대하여, [math]\displaystyle{ \chi'(G) = \Delta(G) = \operatorname{ch}'(G) }[/math]이다. 즉 이분 그래프는 변 채색와 리스트 변 채색(리스트 채색 지표)가 같다.
증명
다음 보조정리에 의해 쉽게 해결된다.
보조정리
[math]\displaystyle{ G }[/math] 위의 유향 그래프 [math]\displaystyle{ D }[/math]에 색들의 집합 [math]\displaystyle{ C }[/math]로의 리스트 배정 [math]\displaystyle{ L:~v\to \mathscr P(C) }[/math]이 주어져 있고,
- [math]\displaystyle{ |L(v)|\ge \operatorname{deg}_D^+ (v) + 1 }[/math] ([math]\displaystyle{ \operatorname{deg}^+ }[/math]는 그 점에서 나가는 차수)
를 만족한다고 하자. 만약 [math]\displaystyle{ D }[/math]가 핵-완전(kernel-perfect)하면, 즉 모든 [math]\displaystyle{ D }[/math]의 유도 부분그래프 [math]\displaystyle{ D' }[/math]이 다음을 만족하는 꼭짓점들의 집합 [math]\displaystyle{ K\subseteq V(D') }[/math](핵)을 가지면 [math]\displaystyle{ D }[/math]는 [math]\displaystyle{ L }[/math]-리스트 채색 가능하다:
- [math]\displaystyle{ K }[/math]는 안정하다. 즉, 어느 두 꼭짓점도 인접해 있지 않다.
- 모든 [math]\displaystyle{ K }[/math]에 있지 않은 꼭짓점 [math]\displaystyle{ u \in V(D') \setminus K }[/math]에 대하여, [math]\displaystyle{ u }[/math]에서 [math]\displaystyle{ K }[/math]로의 변이 존재한다.
보조정리의 증명
[math]\displaystyle{ |V(D)| }[/math]에 대한 귀납법으로 증명한다. [math]\displaystyle{ |V(D)| }[/math]가 최소인 경우는 1일 때이고, 이때는 자명하다. 리스트 배정에 쓰인 색 [math]\displaystyle{ \displaystyle\alpha \in \bigcup_{v\in V(D)} L(v) }[/math]을 택하여, 다음과 같은 유도 부분그래프를 만들자:
- [math]\displaystyle{ D' = D\left[ \left\{v \in V(D):~~ \alpha \in L(v)\right\} \right] }[/math]
[math]\displaystyle{ K }[/math]를 [math]\displaystyle{ D' }[/math]의 핵이라고 하면, [math]\displaystyle{ K }[/math]는 안정하므로 모든 [math]\displaystyle{ K }[/math]의 꼭짓점을 [math]\displaystyle{ \alpha }[/math]로 칠할 수 있다. 이제 [math]\displaystyle{ D'' = D \setminus K }[/math]라고 하면, 핵의 성질에 의해 [math]\displaystyle{ \operatorname{deg}_D^+(v) \ge \operatorname{deg}_{D''}^+ + 1 }[/math]이므로
- [math]\displaystyle{ |L(v) \setminus \{\alpha\}| \ge \operatorname{deg}_{D''}^+ + 1 }[/math]
이다. 귀납법의 가정에 의하여 [math]\displaystyle{ D'' }[/math]는 [math]\displaystyle{ \alpha }[/math]를 사용하지 않는 [math]\displaystyle{ L }[/math]-리스트 채색이 가능하고, 따라서 [math]\displaystyle{ D }[/math] 역시 [math]\displaystyle{ L }[/math]-리스트 채색이 가능하게 된다.