¿El intercambio de un par de bordes de un gráfico reduce su número cromático?

Dejar GRAMO ser un gráfico con número cromático norte sin subgrafo propio de GRAMO tener número cromático norte . Dejar tu , v , w ∈ V ( GRAMO ) ser tal que tu v ∈ mi ( GRAMO ) y tu w ∉ mi ( GRAMO ) . La gráfica GRAMO ′ se obtiene eliminando el tu v borde desde y agregando el tu w borde a GRAMO . ¿Es cierto que el número cromático de GRAMO ′ debe ser norte − 1 ?

Sé que la declaración es verdadera si y solo si hay un color de GRAMO sin el tu v borde (que tiene número cromático norte − 1 ) en el que los vértices tu y w tienen diferentes colores, pero no pude avanzar desde ese punto.

Ha editado el "número mínimo de aristas", eso es bueno, y editado en "gráfico mínimo", que aún no está claro. ¿Es mi 5 ciclos un contraejemplo?
@GerryMyerson sí, lo es. "Gráfico mínimo con número cromático norte "significa un gráfico que no contiene un subgráfico propio con número cromático norte .

Respuestas (2)

Un contraejemplo lo da el ciclo de cinco a − b − C − d − mi − a . Su número cromático es tres. Es mínimo en el sentido de que si elimina cualquier borde, el número cromático se reduce a dos. pero si quitas a − b y poner en a − d entonces el número cromático sigue siendo tres.

Editar: con la definición aclarada en su pregunta, debatí eliminar mi respuesta, pero decidí que podía cambiarla para ofrecer un contraejemplo más pequeño que el sugerido en otras respuestas, siempre que se permitan gráficos no conectados . Si no lo son, creo que esto debería agregarse al enunciado del problema.

Dejar V ( GRAMO ) = { tu , v , w } y mi ( GRAMO ) = { tu v } . GRAMO tiene un solo subgrafo propio que conserva V ( GRAMO ) , con número cromático 1 .

x ( GRAMO ) = 2 . Las únicas aplicaciones posibles de la regla a GRAMO producir mi ( GRAMO ′ ) = { tu w } o mi ( GRAMO ′ ) = { v w } . En cualquier caso x ( GRAMO ′ ) es todavía 2 .

Lo siento, ojos glosados. No me di cuenta de que no eras el OP. Veo. El ejemplo que diste sobre un 5 -cycle tiene el mismo problema, ¿no? ¿Quitar cualquier borde disminuye el número cromático? Sólo pido para asegurarme de que no he perdido su punto.
Reducir el número cromático es un requisito, no un problema. En su ejemplo, el número cromático es dos, y sigue siendo dos después de eliminar un borde; eso es un problema, si mi suposición de lo que OP significa "número mínimo de bordes" es correcta. (En mi ejemplo, el número cromático es tres, y eliminar cualquier borde reduce el número cromático a dos, cumpliendo así el requisito)
¿El intercambio de un par de bordes de un gráfico reduce su número cromático?
RespuestasAquíPolítica de privacidad1y, 0v