Alfredo García Olaverri en el Seminario Rubio de Francia -"Subgrafos planos en trazados topológicos del grafo completo"

Alfredo García Olaverri (Universidad de Zaragoza) impartirá la conferencia: 

"Subgrafos planos en trazados topológicos del grafo completo"

Abstract: La charla trata sobre trazados simples del grafo completo en el plano. Presentamos nuevos resultados estructurales sobre subgrafos planos contenidos en estos trazados. En particular demostramos que cualquier subgrafo plano maximal tiene que ser 2-conexo en vértices, esencialmente 3-conexo en ejes, y tiene que contener al menos 3n/2 ejes. También demostramos que el problema de calcular un subgrafo plano con número máximo de ejes es NP-Duro.

Por otra parte, exponemos nuevas cotas sobre el tamaño mínimo en estos trazados de un subgrafo plano con máximo grado 1 (matching) y de subgrafos camino planos . Estas cotas se obtienen usando una familia especial de trazados del grafo completo, los trazados "twisted" generalizados.

Este es un trabajo conjunto de A. García, J. Tejel (U. de Zaragoza) y O. Aichholzer, A. Pilz, B. Vogtenhuber , A. Weinberger (TU Graz).

___________________________________________________________

Fecha: Jueves, 13 de enero de 2022.
Hora: 12:00 horas.
Lugar: Aula 07, edificio de Matemáticas, primera planta.
Web: http://anamat.unizar.es/seminario.html
http://eventos.unizar.es/52859/detail/seminario-rubio-de-francia.html