Prova do teorema de coloração de linha de Kőnig ( $\chi'(G) = \Delta(G)$)

Dec 06 2020

Estou tentando encontrar uma prova do teorema de coloração de linha de Kőnig , ou seja:

O índice cromático de qualquer gráfico bipartido é igual ao seu grau máximo

Mas, para minha surpresa, eu apenas * consegui encontrar duas perguntas relacionadas ao assunto:

Coloração de bordas de gráficos bipartidos
A coloração das bordas de um gráfico bipartido com um grau máximo de D requer apenas cores D

Como os gráficos são o meu calcanhar de Aquiles, sou incapaz de usar as informações contidas acima para provar $\chi'(G) = \Delta(G)$ Eu mesmo.

* Encontrei muitos artigos referindo-se a ele, mas nenhum comprovando, exceto a página 4 do CH6.pdf da primeira pergunta, mas não acho que seja suficiente.

Respostas

1 Hendrix Dec 06 2020 at 01:38

Tentarei fornecer uma visão geral do conhecimento de pré-requisito e incluir fontes em cada etapa para que você possa entender sequencialmente. Se você não entende certas partes (como a construção no final) eu recomendo que você trabalhe alguns pequenos exemplos.

Vamos primeiro apresentar o Teorema de Hall :

Teorema: (Teorema de Hall) Let $G$ seja um gráfico bipartido com partes $A$ e $B$. Então$G$ tem uma saturação correspondente (conjunto de bordas independente) $A$ (cada vértice de $A$ é o ponto final de alguma aresta na correspondência) se e somente se para cada $X \subseteq A$ temos $|X| \le |N(X)|$.

As duas fontes que recomendo para uma boa visão do teorema de Hall são a Teoria dos Grafos de Diestel (que, se bem me lembro, fornece quatro provas) e a Introdução à Teoria dos Grafos de West.

O significado do Teorema de Hall aqui é que para $k$-Grafos bipartidos regulares, podemos encontrar uma correspondência perfeita. Isso vem de duas coisas:

UMA $k$-Grafo bipartido regular é equilibrado .
UMA $k$-Grafo bipartido regular satisfaz a condição de Hall .

Portanto, agora podemos provar o seguinte:

Lema: se $G$ é um $k$- gráfico bipartido regular, então $\chi'(G) = k$.

Podemos usar indução em $k$. Pelo teorema de Hall,$G$ tem uma combinação perfeita $M$. Considerar$G-M$, qual é $k-1$-regular (por quê?). Pela hipótese de indução,$\chi'(G) = k-1$, e assim podemos adicionar $M$ de volta como uma nova cor, estendendo assim uma adequada $k-1$- coloração de borda de $G-M$ para um adequado $k$- coloração de bordas ativada $G$.

Se você não está familiarizado com a indução, aqui está uma descrição diferente: Removendo uma combinação perfeita de um $k$-Grafo bipartido regular dá uma $k-1$- gráfico regular, que também deve ter uma correspondência perfeita ... Repita este processo $k$ vezes.

Agora, para a linha de chegada. Queremos provar o resultado para qualquer grafo bipartido$G$.

Resultado: se $G$ é um gráfico bipartido, então $\chi'(G) = \Delta(G)$.

E se $G$é regular, então nós terminamos pelo Lema. Caso contrário, há pelo menos um vértice$v$ dentro $G$ com $\deg(v) < \Delta(G)$. Podemos construir um gráfico$R$ de tal modo que

$R$ é bipartido.
$R$ é $\Delta(G)$-regular.
$G \subseteq R$.

Uma construção é a seguinte. Nós temos$G$ bipartido com peças $A$ e $B$. Faça uma cópia de$G$, diga $G'$ com peças $A'$ e $B'$. Então, para cada vértice$v$ não de grau $\Delta(G)$ dentro $G$, adicionamos uma borda entre $v$ e é cópia $v' \in G'$. Este gráfico recém-obtido é bipartido com partes$A \cup B'$ e $B \cup A'$. Repita este processo conforme necessário. Você notará que a cada iteração a lacuna entre o grau mínimo e o grau máximo diminui, então devemos terminar com um$\Delta(G)$- gráfico regular $R$como desejado. Você descobrirá que esta construção é aquela dada pelo comentário de Jon Noel aqui .

Usando o Lema, $\chi'(R) = \Delta(G)$, e, portanto, há uma adequada $\Delta(G)$- coloração de borda de $R$. Desde a$G \subseteq R$, esta coloração adequada funciona para $G$. Ie$\chi'(G) = \Delta(G)$.

Algumas notas.

Observe que usamos o fato geral de que $\chi'(H) \le \chi'(G)$ para $H \subseteq G$ no fim.

Uma coisa que eu dei uma olhada é se estamos permitindo várias arestas, mas as coisas ainda funcionam dessa maneira. Se permitirmos várias arestas, você pode ver por que a maneira como construímos$R$ leva exatamente $1$iteração? Não acredito que haja qualquer razão real para excluir o uso de arestas múltiplas.