갈빈의 이분 리스트 변 채색 정리(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]-리스트 채색이 가능하게 된다.