갈빈의 이분 리스트 변 채색 정리(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(D)\to \mathscr P(C),~v\mapsto L(v)\subseteq 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''}^+(v) + 1 }[/math]이므로
- [math]\displaystyle{ |L(v) \setminus \{\alpha\}| \ge \operatorname{deg}_{D}^+ (v)+ 1 - 1\ge \operatorname{deg}_{D''}^+ (v)+ 1 }[/math]
이다. 귀납법의 가정에 의하여 [math]\displaystyle{ D'' }[/math]는 [math]\displaystyle{ \alpha }[/math]를 사용하지 않는 [math]\displaystyle{ L }[/math]-리스트 채색이 가능하고, 따라서 [math]\displaystyle{ D }[/math] 역시 [math]\displaystyle{ L }[/math]-리스트 채색이 가능하게 된다.
갈빈의 이분 리스트 변 채색 정리의 증명
쾨니그의 정리에 의하여 [math]\displaystyle{ \chi'(G) = \Delta(G) }[/math]이므로, [math]\displaystyle{ \Delta(G) }[/math]-변 채색 [math]\displaystyle{ c }[/math]가 존재한다. 또한 [math]\displaystyle{ \Delta(G) = \operatorname{ch}'(G) }[/math]를 보이면 되므로, 주어진 그래프의 선그래프 [math]\displaystyle{ L(G) }[/math]가 [math]\displaystyle{ \Delta(G) }[/math]-선택 가능함을 보이면 된다. 임의의 리스트 배정 [math]\displaystyle{ L }[/math]이 임의의 꼭짓점 [math]\displaystyle{ v }[/math]에 대하여 [math]\displaystyle{ |L(v)|\le \Delta(G) }[/math]를 만족한다고 하자.
[math]\displaystyle{ G }[/math]는 이분그래프이므로 [math]\displaystyle{ V(G) = X\sqcup Y }[/math]이고 모든 변이 [math]\displaystyle{ X }[/math]와 [math]\displaystyle{ Y }[/math]를 잇는다고 할 수 있다. 이제 선그래프의 변에 다음과 같은 방향을 주자:
- 그래프 [math]\displaystyle{ G }[/math]의 두 변 [math]\displaystyle{ e,~f \in V(L(G)) = E(G) }[/math]이 꼭짓점을 공유하면,
- [math]\displaystyle{ \displaystyle e\to f \Longleftrightarrow \begin{cases} c(e) \lt c(f) & \text{ if they meet at an end in }X \\ c(e) \gt c(f) & \text{ if they meet at an end in }Y \end{cases}. }[/math]
이렇게 준 이유는 차수 조건을 만족시켜야 하기 때문이다. 이 방향에서
- [math]\displaystyle{ \begin{aligned}\operatorname{deg}_D^+ (e)& = |\{f:~c(f)\gt c(e)\land\text{ meeting at }X\}| + |\{f:~c(f)\lt c(e)\land\text{ meeting at }Y\}| \\&\le |\{1,~\cdots,~c(e)-1\}| + |\{c(e)+1,~\cdots,~\Delta(G)\}| \\&= \Delta(G)-1\end{aligned} }[/math]
이므로, 차수 조건이 성립한다. 이제 핵이 있는지 살펴보자. 선그래프에서의 핵은 안정한 변들의 모임이므로, 즉 매칭이다. 선그래프 [math]\displaystyle{ L(G) }[/math]의 유도 부분그래프는 그래프 [math]\displaystyle{ G }[/math]의 어떤 부분그래프 [math]\displaystyle{ H }[/math]의 선그래프 [math]\displaystyle{ L(H) }[/math]에 해당한다. 핵의 두 번째 조건을 선그래프의 관점에서 서술해보면, [math]\displaystyle{ M }[/math]이 선그래프의 핵일 때,
- 모든 [math]\displaystyle{ M }[/math]에 있지 않은 [math]\displaystyle{ e\in E(H)\setminus M }[/math]에 대하여, [math]\displaystyle{ e }[/math]와 [math]\displaystyle{ f \in M }[/math]이 꼭짓점을 공유하며, 선그래프에서의 그 방향은 [math]\displaystyle{ e }[/math]에서 [math]\displaystyle{ f }[/math]이다.
그런데 게일-섀플리 알고리듬에 의하여 이분그래프인 [math]\displaystyle{ H }[/math]는 안정한 매칭 [math]\displaystyle{ M }[/math]이 존재하고, 이때 선호도는 [math]\displaystyle{ x\in X }[/math]가 큰 색을, [math]\displaystyle{ y \in Y }[/math]가 작은 색을 선호한다고 하자. 그러면 [math]\displaystyle{ e\notin M }[/math]이라는 것은 다음 중 하나가 성립함을 말한다:
- [math]\displaystyle{ e }[/math]와 [math]\displaystyle{ X }[/math]에서 만나고 색이 더 큰 [math]\displaystyle{ G }[/math]의 변이 존재한다.
- [math]\displaystyle{ e }[/math]와 [math]\displaystyle{ Y }[/math]에서 만나고 색이 더 작은 [math]\displaystyle{ G }[/math]의 변이 존재한다.
즉, 핵의 두 번째 조건을 성립시킴을 알 수 있다. 따라서 위 보조정리에 의하여 [math]\displaystyle{ L(G) }[/math]는 [math]\displaystyle{ L }[/math]-리스트 채색이 가능하며, [math]\displaystyle{ L(G) }[/math]는 [math]\displaystyle{ \Delta(G) }[/math]-선택가능하다. 따라서
- [math]\displaystyle{ \chi'(G) = \Delta(G) \ge \operatorname{ch}'(G) = \operatorname{ch}(L(G)) \ge \chi(L(G)) = \chi'(G) }[/math]
이므로 셋은 모두 같다. (임의의 그래프 [math]\displaystyle{ G }[/math]에 대하여 [math]\displaystyle{ \chi(G) \le \operatorname{ch}(G) }[/math]임은 정의에 의해 당연하다.)