Minimum degree conditions for monochromatic cycle partitioning in bipartite graphs

Abstract

Si coloreamos con $r$ colores las aristas de un grafo con grado mínimo $n/2 + 1200r\log(n)$ es posible construir una partición del conjunto de vértices, compuesta únicamente ciclos monocromáticos, de tamaño $O(r^2)$. Este resultado, probado por Korándi, Lang, Letzter y Pokrovskiy en \cite{mainpaper:paper}, es el que motiva el estudio de esta tesis. El resultado de que se presenta aquí es una adaptación de la condición de grado mínimo, condicionado a que ahora el grafo estudiado sea bipartito balanceado. Más precisamente, para todo $\eta>0$, para todo grafo bipartito balanceado $r$-arista-coloreado suficientemente grande con grado mínimo $(1/4+\eta)n$, es posible asegurar la existencia de un \textit{vertex cover} de tamaño $O(r^2)$ compuesto únicamente por ciclos monocromáticos vértice disjuntos. Para la demostración del resultado, se presenta el concepto de grafos \textit{birobustamente emparejables} y usamos el lema de regularidad, en su versión de $r$ colores. Posterior a esto, utilizamos un método propuesto por {\oldL}uczak para cubrir casi todo el grafo. Finalizamos utilizando el \textit{``blow-up lemma''} para cubrir los vértices faltantes.