Embbeding de anti-árboles en grafos orientados

Abstract

La pregunta que dio inicio a esta tesis fue decidir si semigrado mínimo mayor a $\frac k2$ en un grafo orientado garantiza tener como subgrafo a cualquier camino orientado de $k$ aristas. Este enunciado correspondería a la extensión natural de un resultado clásico para grafos simples, que en vez de semigrado pide grado mínimo $\frac k2$. El resultado obtenido responde la pregunta para los caminos de largo $k$ cuyas aristas alternan dirección, llamados \textit{anticaminos}, en grafos suficientemente grandes con semigrado mínimo mayor a $\frac k2$, para todo $k\in\mathbb{N}$. Aún mejor, también funciona para todo antiárbol balanceado con $k$ aristas y grado máximo acotado. Para llegar al resultado, se introduce el concepto de \textit{antimatching conexo} y se utiliza el Lema de Regularidad, en su versión para grafos orientados. El proceso de embedding consiste en dividir el antiárbol en unos antiárboles más pequeños y distribuirlos en las aristas del antimatching encontrado en el grafo reducido orientado y hacer las conexiones.