Kőnig의 선 채색 정리 증명 ( $\chi'(G) = \Delta(G)$)
나는 Kőnig의 선 채색 정리의 증거를 찾으려고 노력하고 있습니다 .
이분 그래프의 색도 지수는 최대 차수와 같습니다.
그러나 놀랍게도 주제와 관련된 두 가지 질문 만 찾을 수있었습니다.
- 이분 그래프의 가장자리 채색
- 최대 D 차가있는 이분 그래프의 모서리 색상에는 D 색상 만 필요합니다.
그래프는 내 아킬레스 건이기 때문에 위의 정보를 사용하여 증명할 수 없습니다. $\chi'(G) = \Delta(G)$ 자기.
* 나는 그것을 언급하는 많은 논문을 찾았지만 첫 번째 질문에서 CH6.pdf의 4 페이지를 제외하고는 입증 되지 않았지만 충분하다고 생각하지 않습니다.
답변
필자는 사전 지식에 대한 개요를 시도하고 제공하고 순차적으로 이해할 수 있도록 각 단계에서 소스를 포함합니다. 특정 부분 (마지막 구조 등)을 이해하지 못하는 경우 몇 가지 작은 예를 사용하는 것이 좋습니다.
먼저 Hall 's Theorem을 소개하겠습니다 .
정리 : (홀의 정리) Let $G$ 부분이있는 이분 그래프 $A$ 과 $B$. 그때$G$ 일치하는 (독립적 인 모서리 세트) 포화 $A$ (모든 정점 $A$ 일치하는 일부 모서리의 끝점) $X \subseteq A$ 우리는 $|X| \le |N(X)|$.
Hall의 정리를 잘보기 위해 제가 추천하는 두 가지 소스는 Diestel의 Graph Theory (내가 기억한다면 4 개의 증명을 제공함)와 West의 Graph Theory 소개입니다.
여기에서 Hall의 정리의 중요성은 $k$-정규 이분 그래프, 완벽한 매칭을 찾을 수 있습니다. 이것은 두 가지에서 비롯됩니다.
- ㅏ $k$-정규 이분 그래프가 균형을 이룹니다 .
- ㅏ $k$-정규 이분 그래프 는 Hall의 조건을 만족합니다 .
이제 다음을 증명할 수 있습니다.
정리 : If $G$ 이다 $k$-정규 이분 그래프 $\chi'(G) = k$.
우리는 $k$. 홀의 정리에 의해,$G$ 완벽하게 일치합니다 $M$. 중히 여기다$G-M$, 즉 $k-1$-일반 (왜?). 귀납 가설에 따르면$\chi'(G) = k-1$, 그래서 우리는 $M$ 다시 새로운 색상으로, 따라서 적절한 확장 $k-1$-가장자리 착색 $G-M$ 적절한 $k$-가장자리 착색 켜기 $G$.
귀납법에 익숙하지 않은 경우 다른 설명이 있습니다. $k$-정규 이분 그래프는 $k-1$-완벽하게 일치해야하는 일반 그래프 ...이 프로세스를 반복합니다. $k$ 타임스.
이제 결승선입니다. 우리의 결과 입증 할 어떤 이분 그래프$G$.
결과 : 만약 $G$ 이분 그래프입니다. $\chi'(G) = \Delta(G)$.
만약 $G$규칙적이라면 우리는 Lemma에 의해 끝납니다. 그렇지 않으면 적어도 하나의 정점이 있습니다.$v$ 에 $G$ 와 $\deg(v) < \Delta(G)$. 그래프를 만들 수 있습니다$R$ 그런
- $R$ 이분입니다.
- $R$ 이다 $\Delta(G)$-정규병.
- $G \subseteq R$.
하나의 구성은 다음과 같습니다. 우리는$G$ 부분으로 이분 $A$ 과 $B$. 사본 가져 오기$G$, 말 $G'$ 부품 포함 $A'$ 과 $B'$. 그런 다음 각 정점에 대해$v$ 정도가 아니다 $\Delta(G)$ 에 $G$, 우리는 사이에 가장자리를 추가합니다 $v$ 그리고 그것은 사본입니다 $v' \in G'$. 새로 얻은이 그래프는 부분으로 나누어 져 있습니다.$A \cup B'$ 과 $B \cup A'$. 필요에 따라이 과정을 반복합니다. 반복 할 때마다 최소 차수와 최대 차수 사이의 간격이 감소하는 것을 알 수 있습니다.$\Delta(G)$-일반 그래프 $R$바라는대로. 이 구성이 여기 에있는 Jon Noel의 의견에 의해 제공된 것임을 알 수 있습니다 .
Lemma를 사용하여 $\chi'(R) = \Delta(G)$, 따라서 적절한 $\Delta(G)$-가장자리 착색 $R$. 이후$G \subseteq R$,이 적절한 색상은 $G$. 즉$\chi'(G) = \Delta(G)$.
몇 가지 메모.
일반적인 사실을 사용했습니다. $\chi'(H) \le \chi'(G)$ ...에 대한 $H \subseteq G$ 끝에.
내가 훑어 본 한 가지는 다중 에지를 허용하지만 상황이 여전히 그렇게 작동하는지 여부입니다. 여러 모서리를 허용하면 우리가 구성한 방식이$R$ 정확히 걸립니다 $1$되풀이? 다중 모서리 사용을 배제 할 실제 이유가 없다고 생각합니다.
한 가지 중요한 점은 엣지 컬러링의 색상 클래스를 매칭이라고 생각하는 것입니다.