Teoría de grafos: Demostrar $k$ -Gráfico regular $\#V$ = impar, $\chi'(G)> k$

Question

Estoy buscando probar que cualquier $k$ -Gráfico regular $G$ (es decir, un gráfico con grado $k$ para todos los vértices) con un número impar de puntos tiene número de coloración de aristas $>k$ ( $\chi'(G) > k$ ).

Con Vizing, veo que $\chi'(G) \leq k + 1$ Así que aparentemente $\chi'(G)$ acabará siendo igual a $k+1$ .

Además, como $\#V$ es impar, $k$ debe ser uniforme para $\#V\cdot k$ sea un número par (se requiere que sea par, ya que $\frac{1}{2}\cdot\#V\cdot k = \#E$ .

¿Alguien tiene alguna sugerencia sobre qué probar?

Answer 1

Dejemos que $G=\langle V,E\rangle$ ser un $k$ -grafo regular con $n=2m+1$ vértices; como usted dice, claramente $k=2\ell$ para algunos $\ell$ Así que $G$ tiene $$\frac{kn}2=\frac{2\ell(2m+1)}2=\ell(2m+1)$$ bordes. Supongamos que $c:E\to\{1,\dots,k\}$ es una coloración de las aristas de $G$ . $$\frac{\ell(2m+1)}k=m+\frac12\;,$$ por lo que hay algún color que se utiliza en al menos $m+1$ bordes. $G$ sólo tiene $2m+1$ vértices, por lo que dos de estas aristas deben compartir un vértice, y $c$ por lo tanto, no puede ser una coloración adecuada.

Answer 2

Otra forma de demostrar este hecho es observar que en cualquier coloración de aristas adecuada, cada conjunto de aristas que comparten un color debe formar un emparejamiento. Pero para cualquier color dado, el emparejamiento toca un número par de vértices, por lo que debe haber un vértice que no tenga ese color. Como ese vértice tiene $k$ bordes, todos de diferente color, juntos debe haber al menos $k + 1$ colores.