Usted está aquí: Inicio / Actividades / Seminarios / Seminario Preguntón de Matemáticas Discretas / Actividades / Caracterización de cográficas polares por medio de subgráficas prohibidas

Caracterización de cográficas polares por medio de subgráficas prohibidas

Ponente: Fernando Esteban Contreras Mendoza
Institución: Posgrado en Ciencias Matemáticas UNAM
Tipo de Evento: Investigación, Formación de Recursos Humanos
Cuándo 15/01/2019
de 17:00 a 18:00
Dónde Unidad Multidisciplinaria de Docencia e Investigación (UMDI), Aula 2. UNAM Campus Juriquilla, Querétaro
Agregar evento al calendario vCal
iCal

Una cográfica es una gráfica que no tiene trayectorias de cuatro vértices como subgráficas inducidas. La familia de las cográficas ha sido bien estudiada y se conocen muchas interesantes propiedades de ella; en particular, muchos problemas que son difíciles de resolver para gráficas generales admiten una sencilla solución cuando se restringen a las cográficas.

Una generalización al problema de coloración propia de los vértices de una gráfica es el de las llamadas gráficas polares: se dice que una gráfica es (s, k)-polar si existe una bipartición de su conjunto de vértices tal que una de las partes induce una gráfica multipartita completa con a lo más s partes, y la otra parte induce la unión ajena de a lo más k gráficas completas.

En esta charla vamos a hablar sobre las familias de cográficas que son (s, 1)-polares, específicamente, sobre una construcción recursiva que permite la caracterización de dichas familias de gráficas a través de subgráficas prohibidas.