De ciclos dirigidos a ciclos arcoíris

Ponente(s): Diego Antonio Gonzalez Moreno

Los problemas sobre la existencia de ciclos dirigidos en digráficas han motivado importantes conjeturas y resultados en teoría de gráficas, como la conjetura de Caccetta--Häggkvist, que afirma que toda digráfica $D$ de orden $n$ con $\delta^+(D) \geq k$ contiene un ciclo de longitud a lo más $n/k$, o la conjetura de Bermond--Thomassen, que establece que toda digráfica $D$ de exgrado al menos $2k-1$ contiene $k$ ciclos disjuntos. En esta charla veremos una idea propuesta por Ron Aharoni, Matthew DeVos y Ron Holzman [2019] para transformar ciertos problemas sobre ciclos dirigidos en problemas equivalentes o análogos sobre la existencia de ciclos arcoíris en gráficas con aristas coloreadas, así como algunas aplicaciones de los resultados que se obtienen mediante esta perspectiva.