Prueba del teorema de coloración de líneas de Kőnig ( $\chi'(G) = \Delta(G)$)

Dec 06 2020

Estoy tratando de encontrar una prueba del teorema de coloración de líneas de Kőnig , es decir:

El índice cromático de cualquier gráfico bipartito es igual a su grado máximo

Pero para mi sorpresa, solo * he podido encontrar dos preguntas relacionadas con el tema:

Coloración de bordes de gráficos bipartitos
La coloración de los bordes de un gráfico bipartito con un grado máximo de D solo requiere colores D

Como los gráficos son mi talón de Aquiles, soy incapaz de usar la información contenida en lo anterior para demostrar $\chi'(G) = \Delta(G)$ yo mismo.

* He encontrado muchos artículos que se refieren a él, pero ninguno lo prueba, a excepción de la página 4 de CH6.pdf de la primera pregunta, pero no creo que sea suficiente.

Respuestas

1 Hendrix Dec 06 2020 at 01:38

Intentaré dar una descripción general de los conocimientos previos e incluiré fuentes en cada paso para que pueda comprenderlas secuencialmente. Si no entiendes ciertas partes (como la construcción al final) te recomiendo que trabajes con algunos pequeños ejemplos.

Primero introduzcamos el teorema de Hall :

Teorema: (Teorema de Hall) Sea $G$ ser un gráfico bipartito con partes $A$ y $B$. Entonces$G$ tiene una saturación coincidente (conjunto de bordes independientes) $A$ (cada vértice de $A$ es el punto final de alguna ventaja en la coincidencia) si y solo si para cada $X \subseteq A$ tenemos $|X| \le |N(X)|$.

Las dos fuentes que recomiendo para tener una buena visión del teorema de Hall son la teoría de grafos de Diestel (que, si mal no recuerdo, da cuatro pruebas) y la introducción de West a la teoría de grafos.

El significado del teorema de Hall aquí es que para $k$-Gráficos bipartitos regulares, podemos encontrar una coincidencia perfecta. Esto proviene de dos cosas:

UN $k$-El gráfico bipartito regular está equilibrado .
UN $k$-Gráfico bipartito regular satisface la condición de Hall .

Entonces ahora podemos probar lo siguiente:

Lema: Si $G$ es un $k$-Gráfico bipartito regular, luego $\chi'(G) = k$.

Podemos utilizar la inducción en $k$. Según el teorema de Hall,$G$ tiene una combinación perfecta $M$. Considerar$G-M$, cual es $k-1$-regular (¿por qué?). Por la hipótesis de inducción,$\chi'(G) = k-1$, y así podemos agregar $M$ volver como un nuevo color, extendiendo por lo tanto un adecuado $k-1$-color de borde de $G-M$ a un adecuado $k$-color de borde en $G$.

Si no está familiarizado con la inducción, aquí hay una descripción diferente: Eliminar una coincidencia perfecta de un $k$-Gráfico bipartito regular da un $k-1$-Gráfico regular, que también debe tener una coincidencia perfecta ... Itere este proceso $k$ veces.

Ahora para la línea de meta. Queremos demostrar el resultado de cualquier gráfico bipartito.$G$.

Resultado: Si $G$ es un gráfico bipartito, entonces $\chi'(G) = \Delta(G)$.

Si $G$es regular, entonces hemos terminado con el Lema. De lo contrario, hay al menos un vértice$v$ en $G$ con $\deg(v) < \Delta(G)$. Podemos construir una gráfica$R$ tal que

$R$ es bipartito.
$R$ es $\Delta(G)$-regular.
$G \subseteq R$.

Una construcción es la siguiente. Tenemos$G$ bipartito con partes $A$ y $B$. Toma una copia de$G$decir $G'$ con partes $A'$ y $B'$. Entonces para cada vértice$v$ no de grado $\Delta(G)$ en $G$, agregamos una ventaja entre $v$ y es copia $v' \in G'$. Este gráfico recién obtenido es bipartito con partes$A \cup B'$ y $B \cup A'$. Repita este proceso según sea necesario. Notarás que en cada iteración la brecha entre el grado mínimo y el grado máximo disminuye, por lo que debemos terminar con un$\Delta(G)$-Gráfico regular $R$como se desee. Encontrarás que esta construcción es la que da el comentario de Jon Noel aquí .

Usando el lema, $\chi'(R) = \Delta(G)$, y por lo tanto hay un $\Delta(G)$-color de borde de $R$. Ya que$G \subseteq R$, esta coloración adecuada funciona para $G$. Es decir$\chi'(G) = \Delta(G)$.

Algunas notas.

Tenga en cuenta que usamos el hecho general de que $\chi'(H) \le \chi'(G)$ para $H \subseteq G$ al final.

Una cosa que sí miré es si permitimos múltiples bordes, pero las cosas aún funcionan de esa manera. Si permitimos múltiples aristas, ¿puede ver por qué la forma en que hemos construido$R$ toma exactamente $1$¿iteración? No creo que haya ninguna razón real para excluir el uso de múltiples aristas.