Condiciones de grado mínimo para subdivisiones generadoras.

Resumen: En esta charla mostraremos que en todo grafo con n vértices y grado mínimo ligeramente por sobre n/2 es posible encontrar la subdivisión de un grafo completo, la que además usa todos los vértices del grafo huésped y donde cada arista está subdividida casi la misma cantidad de veces. La demostración es completamente probabilista y no usa ningún tipo de argumento tipo absorción o regularidad.

Posted on Oct 11, 2023 in Seminario de Grafos, Seminars