El teorema 10.10 del libro de texto "A First Course in Graph Theory (2012)" de Gary Chartrand y Ping Zhang es el siguiente:
Por cada entero , existe un gráfico libre de triángulos con número cromático .
Esto se demuestra por inducción sobre y en el paso inductivo en realidad muestra que
A partir de una -grafo sin triangulo cromatico , la construcción de Mycielski produce una -grafo sin triangulo cromatico .
La construcción de Mycielski (wiki) de se obtiene de sumando primero, para cada vértice de , un nuevo vértice , llamado el vértice de la sombra de , y unirse a los vecinos de en y luego agregar un nuevo vértice y unirse a todos los vértices de la sombra.
Por la parte la corrección de , se procede de la siguiente manera:
Supongamos, por el contrario, que . Que haya un -colorante de , decir con colores . Podemos suponer que . Desde es adyacente a cada vértice de la sombra en , se sigue que los vértices de las sombras están coloreados con los colores . Por cada vértice de la sombra de , el color es diferente de los colores asignados a los vecinos de . Por lo tanto, si para cada vetex de perteneciendo a , el color es reemplazado por , tenemos una -coloración de . Esto es imposible, sin embargo, ya que .
Mi problema: el argumento en negrita no me parece claro. ¿Cómo asegurarse de que la coloración resultante sea una coloración adecuada? En otras palabras, cómo mostrar que para cada par de vértices adyacentes en , ?
Creo que la prueba en ese libro podría ser defectuosa.
Si y son vértices adyacentes de tal que sus vértices de sombra tienen el mismo color (es decir ), luego reemplazar los colores como en la prueba no dará una coloración adecuada.
No hay ninguna razón (obvia para mí) por la que esto no pueda suceder.
Ambas respuestas ignoran este problema al suponer que si un vértice cambia de color, ninguno de sus vecinos lo hace.
Para solucionar esto, solo cambie el color de los vértices de que tienen el mismo color que . (Y cambiar su color por el de su sombra, como en el libro.) Se puede comprobar que esta es una coloración adecuada de .
La demostración pretende mostrar y tiene dos partes.
En primer lugar, muestran que .
La segunda parte de la demostración muestra que . Esta es la parte que se refiere al argumento en negrita en su publicación.
Para probar esto, los autores suponen BWOC, que . Entonces hay un coloración de . el vértice se puede colorear usando el color y los vértices de la sombra se pueden colorear usando colores.
En este punto entra la afirmación en negrita: por lo tanto, si para cada vetex 𝑦 de 𝐺 perteneciente a 𝐹, el color 𝑐(𝑦) se reemplaza por 𝑐(𝑦′), tenemos una coloración (𝑘−2) de 𝐹.
Los autores están diciendo para dar a cada vértice en del mismo color que su vértice de sombra . ¿Por qué sabemos que esta es una coloración adecuada? Como todo vértice adyacente a en también es adyacente a en , entonces debe tener un color diferente a cada vecino de .
Este hecho esencialmente dice que si tenemos un coloración de , no tenemos que usar el color de (es decir ) para cualquiera de los vértices de . Así tendríamos una adecuada coloración de que es la contradicción buscada.
Basado en la suposición de que , desde sólo es adyacente al conjunto de vértices de sombra de , sabemos que el conjunto de vértices de la sombra es de colores.
Ahora para abordar su pregunta; Al aplicar una coloración adecuada a un gráfico construido de Mycielski, es posible asignar . Es decir, un vértice de sombra. puede tener el mismo color que . Esto se debe a que cada sombra no es adyacente a su origen en el gráfico construido.
Por lo tanto, debido a que el conjunto de vértices de la sombra es coloreable, sin colores ya impuestos , coloreamos de modo que para cada . Así, proporcionando un colorear en lo que contradice cómo Fue definido.
Misha Lavrov