La primera charla será el martes 01/04.

Expositora: Ayelén Dinkel

Título: Thinness condicionada a órdenes canónicos de ciertas clases de grafos.

Resumen:

La teoría estructural de grafos consiste en la caracterización de distintas clases de grafos por medio de subgrafos inducidos prohibidos, propiedades de descomposición o de orden de vértices, patrones prohibidos, comportamiento de ciertos parámetros, como por ejemplo los parámetros de ancho.
Ese tipo de caracterizaciones o propiedades son las que habitualmente se utilizan para el desarrollo de algoritmos eficientes dentro de la clase para problemas de optimización combinatoria que son NP-completos.
En este trabajo nos enfocamos en la caracterización por patrones prohibidos de las clases de grafos definidas por su thinness, uno de los parámetros de ancho en grafos definidos en la literatura.
Caracterizamos por patrones prohibidos minimales a la clase de grafos co-bipartitos con thinness condicionada a lo sumo 2.
También mostramos propiedades que cumple esta familia de grafos cuando conocemos un orden y partición consistentes en dos clases.

Son todos bienvenidos y si están interesados en participar frecuentemente en este seminario, los invitamos a unirse a nuestro grupo de Telegram: https://t.me/+RkVxwjjIdiE1Yjkx y visitar la página del seminario: https://web.dm.uba.ar/index.php/investigacion/seminarios/seminario-grafos .