Pregunta sobre la coloración de las aristas y los emparejamientos perfectos en los grafos regulares

Question

En el página wiki para la coloración de los bordes dice las dos cosas siguientes:

1. "Si el tamaño de un emparejamiento máximo en un grafo dado es pequeño, se necesitarán muchos emparejamientos para cubrir todas las aristas del grafo. Expresado de manera más formal, este razonamiento implica que si un grafo tiene m aristas en total, y si a lo sumo las aristas pueden pertenecer a un emparejamiento máximo, entonces cada coloración de aristas del grafo debe utilizar al menos m/ colores diferentes."
2. "Para un gráfico regular de grado $k$ que no tiene una coincidencia perfecta, este límite inferior puede utilizarse para demostrar que al menos $k + 1$ se necesitan colores".

¿Puede alguien explicar el segundo punto?

También dice que un grafo regular tiene una 1-factorización (descomposición en emparejamientos perfectos) si y sólo si tiene índice cromático igual a $\Delta(G)$ . Comprendo el sentido de avance (la descomposición te da la coloración), pero ¿por qué es cierta la implicación inversa?

Answer 1

Un gráfico regular de grado $k$ con $n$ vértices tiene $nk/2$ bordes. Una coincidencia perfecta tiene $n/2$ bordes, por lo que $(nk/2)\div(n/2)=k$ los colores serían suficientes, si se pudiera factorizar el gráfico en combinaciones perfectas. Si no hay coincidencias perfectas, necesitas más colores --- al menos $k+1$ .

Answer 2

Reclamar: Que $G$ ser un $k$ -regular. Entonces $G$ tiene una 1-factorización si $G$ tiene un borde $k$ -Coloración.

Pf. => Sea $F$ sea una 1-factorización de $G$ . Para cada coincidencia perfecta $M$ en $F$ asignar a las aristas en $M$ un color distinto $c_M$ . Es evidente que se trata de un borde $k$ -coloración de $G$ .

<= Let $C$ sea una arista $k$ -coloración de $G$ . Para cada color $c$ asignado por $C$ los bordes coloreados $c$ por $C$ forman una combinación perfecta en $G$ . Esto da $k$ coincidencias perfectas que son disjuntas en los bordes, que es una factorización de 1 de $G$ . QED