La ilustración de Página de Wolfram pretende presentar un grafo sin triángulos y de coloración única. Sin embargo, esto parece ser descaradamente falso: el gráfico tiene una simetría con respecto a una reflexión a través del eje horizontal, y podemos utilizar esta simetría para construir una nueva coloración no isomorfa a la original.
¿Me estoy perdiendo algo obvio aquí, o la ilustración es simplemente errónea? Si es esto último, ¿cuál es un ejemplo sencillo de un gráfico sin triángulos y únicamente con tres colores?
2 votos
Mi teoría de grafos es débil, y como tal no me resulta obvio por qué la simetría reflexiva debería garantizar una coloración no isomorfa a la original. ¿Puedes explicarlo un poco o proporcionar una referencia?
0 votos
@J.Loreaux Según la definición de Wolfram (y creo que es la definición habitual) dos coloraciones son distintas si dan una partición diferente (ver la página enlazada, primera definición).
1 votos
¿Alguien ha informado a los responsables del sitio web sobre el error?
0 votos
@MarkS. Acabo de hacerlo.
0 votos
Por cierto, es bastante irónico que la entrada de Wolfram que se está discutiendo mencione específicamente dos casos de la literatura en los que se dan ejemplos incorrectos de gráficos unicolores, y hace un punto para explicar por qué son incorrectos.
0 votos
Pero la simetría izquierda-derecha del espejo (incluso con el borde extra mencionado en Respuesta de n55 ¿corresponde simplemente a intercambiar el rojo y el verde y, por tanto, a conservar la partición?
1 votos
@DavidRicherby: El tema no es la simetría izquierda-derecha, sino la simetría arriba-abajo. La simetría derecha-izquierda es efectivamente inofensiva.