El teorema de Baranyai nos dice que un$K_n$ puede colorearse con$n-1$ colores siempre que$n$ sea parejo; el lema del handshaking hace que sea fácil mostrar que no es posible cuando$n$ es impar. No es difícil verificar que para$n=4$ o$n=6$ este color es único hasta el isomorfismo (donde se nos permite reordenar los vértices y volver a etiquetar los colores). ¿Es esto siempre cierto? ¿Hay más grandes, incluso,$n$, donde hay múltiples coloraciones distintas?
Respuesta
¿Demasiados anuncios?
Si $n$ es par, entonces el resultado de esta respuesta, cada $(n-1)$-edge-colorante de $K_n$ corresponde a un simétrica $n-1$ $n-1$ cuadrado latino.
El número de simétrica cuadrados latinos crece mucho más rápido que el número de simetrías de un $(n-1)$-edge-colorear, así que para un gran $n$ habrá muchas posibilidades de colorantes.
Para $n=8$, no es demasiado difícil encontrar un ejemplo de dos personas que no son isomorfos borde de colores. Por un lado, existe la norma de construcción (que se muestra a continuación), que implica la rotación de los mismos perfecto maridaje a través de múltiplos de $\frac{2\pi}{7}$ radianes. Se puede comprobar que en esa construcción, que es la unión de dos perfecto matchings es un ciclo Hamiltoniano. (Debido a la simetría de rotación, sólo hay tres casos a considerar.)
Por otro lado, si usted comienza un borde para colorear tomando dos perfecto matchings cuya unión es de dos a $4$-ciclos, no debería ser difícil de completar que a un $7$-edge-colorante de $K_8$. Me hizo bastante arbitraria, y consiguió el colorante a continuación:
Debido a que la propiedad "hay dos colores de cuya unión no es un ciclo Hamiltoniano?" es preservada por isomorfismo, estos dos colorantes no son isomorfos.
