Asigne una lista L (x) de tamaño dos a cada vértice x de un ciclo impar. Demuestre que hay un colorante L a menos que todos los conjuntos L (x) sean iguales.

Question

El problema anterior es de un examen intermedio que tomé en mi clase de teoría de grafos y no sabía cómo responderlo. Esperaba obtener algunos consejos para comprender mejor el problema y escribirlo. ¡Gracias de antemano!

Answer 1

Empiece por encontrar dos nodos adyacentes cuyas listas son desiguales. Dicen que estos son $v$ e $w$, donde $v$ es hacia la derecha de $w$. Asignar a $v$ un color que no está presente en $w$'s de la lista. Entonces, comenzando con $v$'s de las agujas del reloj vecino, y proceder a la derecha de todo el ciclo, asignar a cada nodo de un color diferente de su sentido anti-horario vecino. Esto es posible (por qué?). Además, al llegar a la $w$ al final, $w$'s de color será diferente de su sentido anti-horario vecino, y diferentes a los de $v$ (debido a $v$'s de color no está aún en $w$'s de la lista).