Caracterización de cográficas polares por medio de subgráficas prohibidas
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.
