Dos ciclos que cubren vértices

Question

Considero un grafo coloreado con los colores rojo y azul. Gyarfas demostró en su paper http://www.renyi.hu/~gyarfas/Cikkek/16_Gyarfas_VertexCoveringsByMonochromaticPathsAndCycles.pdf la existencia de dos ciclos que cubren los vértices e intersectan en a lo sumo un vértice.

Él consideró el camino más largo que consiste en un camino rojo seguido por un camino azul (dicho camino $P$ es hamiltoniano). Si un vértice $v$ no está cubierto, debe ser unido en azul al origen de $P$ y en rojo al final de $P$. Luego se pueden cubrir los vértices de $P$ y $v$ usando el borde desde el punto de inicio de $P$ al punto final (llamémoslos $a$ y $b$). Por lo tanto, existe un ciclo monocromático $C$ y un camino monocromático $P$ con colores diferentes que particionan el conjunto de vértices.

Pido ayuda con el dibujo. Creo que se ve como pero ¿dónde está el ciclo $C$?

Answer 1

Lo que Bessy y Thomasse están discutiendo en su segundo párrafo es lo siguiente:

Lema. Sea $n\geq 2$. Para cada coloración de $E(K_n)$ en dos colores, existe un ciclo monocromático $C$ de tamaño al menos dos y un camino monocromático $P$, coloreado de manera diferente a $C$, tal que $P$ y $C$ son disjuntos en vértices y $V(P)\cup V(C)=V(K_n)$.

Cabe destacar que están considerando conjuntos vacíos, vértices singleton y aristas como ciclos, y conjuntos vacíos como caminos.

Justifican el lema en tres pasos y creo que quizás tu problema es que estás confundiendo la demostración de lo anterior con la demostración del primer paso de estos. En todo caso, aquí tienes una prueba más detallada.

Paso 1: Existe un camino hamiltoniano $H$ tal que $H$ consiste en un camino rojo seguido por un camino azul.

Prueba: Llamemos a cualquier camino que consista en un camino rojo seguido por un camino azul un camino "rojo-azul". Luego demostramos que cualquier camino rojo-azul que no sea un camino hamiltoniano siempre se puede extender a un camino rojo-azul más largo.

Para hacer esto, supongamos que $Q$ es un camino rojo-azul, digamos de $a$ a $b$ pero que hay un vértice $v$ que no está en $Q$. Algo similar a la siguiente imagen (la misma que la tuya pero dibujada de manera un poco diferente. $Q$ corre a lo largo de la parte superior aquí):

(Nótese que no hay un $C$ en esta imagen. Esa parte viene más tarde.)

Ahora consideramos la arista $ab$. Si es roja, entonces obtenemos un camino rojo-azul más largo como se muestra en verde aquí:

Si $ab$ es azul, entonces obtenemos un camino rojo-azul más largo como se muestra en verde aquí:

Esto completa la prueba del Paso 1.

Paso 2: Existe un cycle hamiltoniano que consiste en un único camino rojo y un camino azul.

Prueba: Tomamos un camino hamiltoniano rojo-azul $Q$, digamos de $x$ a $y$, luego dado que $xy$ es rojo o azul, debemos tener que $Q\cup xy$ es un ciclo hamiltoniano rojo-azul. Esto completa la prueba del Paso 2.

Prueba del Lema: Sea $H=(v_1,\ldots,v_n)$ un ciclo hamiltoniano que consiste en un único camino rojo, digamos $(v_1,v_2,\ldots,v_k)$ y un camino azul $(v_k,v_{k+1},\ldots,v_n,v_1)$.

Si $H$ es todo de un color, entonces tomamos $C=H$ y $P=\emptyset$. Nótese que esto también se encarga del caso $n=2$, así que podemos asumir $n\geq 3$ y que $H$ tiene al menos dos colores.

Consideremos la arista $e$ entre $v_1$ y $v_k$. Si esta arista es roja, entonces tomamos $C$ como el ciclo rojo $(v_1,v_2,\ldots,v_k,v_1)$ y tomamos $P$ como el camino azul $(v_{k+1},v_{k+2},\ldots, v_n)$. Si $e$ es azul, tomamos $C$ como el ciclo azul $( v_1,v_k,v_{k+1},\ldots,v_n,v_1)$ y $P$ como el camino rojo $(v_2,\ldots,v_{k-1})$. En cualquier caso, $C$ contiene a $e$ y por lo tanto tiene una longitud de al menos $2$.