Número cromático total de ciclos

Según Wikipedia, en la teoría de grafos, la coloración total es un tipo de coloración de gráficos en los vértices y bordes de un gráfico. Cuando se usa sin ninguna calificación, siempre se supone que una coloración total es adecuada en el sentido de que no se asigna el mismo color a ningún borde adyacente ni a ningún borde ni a sus vértices finales.

Nota: Solo para aclarar la definición...
En coloración total, ningún vértice adyacente tiene el mismo color.

El número cromático total x ″ ( GRAMO ) de un gráfico GRAMO es el menor número de colores necesarios en cualquier coloración total de GRAMO .

Pregunta: Demostrar que si norte es múltiplo de 3,   x ″ ( C norte ) = 3 y de lo contrario,   x ″ ( C norte ) = 4 .

Nota: No tengo idea de cómo probar esto. Pero sé que x ″ ( GRAMO ) ≥ Δ ( GRAMO ) + 1 .

Gracias de antemano.

Como parte de la definición de una coloración total (adecuada), ¿no quiere decir también que no se asigna el mismo color a ningún vértice adyacente ?
@bof Escribí que asumimos que la coloración total siempre es adecuada :)
No, usted escribió que "siempre se supone que la coloración total es adecuada en el sentido de que no se asigna el mismo color a ningún borde adyacente ni a ningún borde ni a sus vértices finales".
@bof hice la edición :) ¿estás satisfecho ahora amigo? :) también... esa definición era de Wikipedia... solo quería escribir una buena definición y es por eso que algunas personas dicen que no siempre podemos confiar en Wikipedia :) de todos modos... gracias :)
¿ Usaste una cita no atribuida de Wikipedia? Que deplorable.
@bof ahora se atribuye :) ¿algún otro problema? Me encantaría escuchar y corregir mis errores :)

Respuestas (1)

Primero establecemos el límite superior exhibiendo una coloración 3-(total-) para C norte cuando 3 ∣ norte y un 4-colorear para todos norte .

Cuando norte ∣ 3 colorea los vértices rojo, verde, azul cíclicamente. Colorea el borde entre dos vértices con el único color que no se usa en sus extremos. Esta es una coloración total adecuada con 3 colores (¡compruébalo!).

Cuando norte es incluso coloreamos alternativamente los vértices con rojo y verde, y alternativamente coloreamos los bordes con azul y amarillo. Esta es una coloración total adecuada con 4 colores (¡compruébalo!).

Cuando norte Es raro que vayamos en el sentido de las agujas del reloj alrededor del ciclo y empecemos a colorear los vértices alternativamente con rojo y verde. El último vértice causaría dos vértices rojos adyacentes, así que lo coloreamos de azul. Ahora volvemos a recorrer el ciclo y cuando pasamos de un vértice rojo a uno verde, coloreamos el borde de azul, cuando pasamos de un vértice verde a uno rojo, coloreamos el borde de azul, cuando pasamos de un vértice verde a uno azul (solo una vez) coloreamos el borde rojo y cuando pasamos de un vértice azul a uno rojo (solo una vez) coloreamos el borde verde. Esta es una coloración total adecuada con 4 colores (¡compruébalo!).

Desde x ″ ( GRAMO ) ≥ Δ ( GRAMO ) + 1 = 3 ya hemos terminado con el caso 3 ∣ norte .

Para la última parte, necesitamos mostrar que no es posible una coloración total de 3 adecuada, a menos que norte es múltiplo de 3.

Dejar v 1 , … , v norte ser los vértices de C norte y supongamos que tenemos un 3-coloreado adecuado. v 1 , v 2 y borde v 1 v 2 debe tener todos los colores diferentes, digamos rojo, verde, azul respectivamente. Ahora borde v 2 v 3 no puede ser verde o azul, por lo que debe ser rojo. Vértice v 3 no puede ser verde o rojo, por lo que debe ser azul. Continuando con este proceso, verá que todo el coloreado es forzado y que terminamos con un coloreado cíclico de los vértices con el período tres tal como lo usamos arriba (¡verifique!). Evidentemente, esto sólo es posible cuando norte es múltiplo de 3.

De acuerdo con la definición de OP de coloración total, x ″ ( C 2 norte ) = 3 ; podemos colorear las aristas alternativamente de rojo y azul, y colorear todos los vértices de verde.
Por supuesto, de acuerdo con otra definición de coloración total que he visto en otra parte, los vértices adyacentes también deben tener diferentes colores, y así x ″ ( C norte ) = x ( C 2 norte 2 ) .
@bof: Debo admitir que pasé por alto la definición no estándar que dio el OP, pero incluso si lo hubiera notado, habría asumido que el OP simplemente cometió un error al escribir la definición de coloración total: nadie define la coloración total. forma en que lo hizo.
@LeenDroogendijk esa definición no fue mía, amigo :) eso fue de Wikipedia en.wikipedia.org/wiki/Total_coloring ... pero lo que quise decir fue claro :) y ves que incluso Wikipedia define el color total de esa manera :) ) por lo que no es cierto que "nadie define el coloreado total como lo hizo Wikipedia" :)) gracias por la respuesta :)
Tú ganas :) Esa es la definición de Wikipedia. como mínimo, ambiguo, ya que fácilmente puede interpretarse incorrectamente.
Número cromático total de ciclos
RespuestasAquíPolítica de privacidad1y, 0v