Caracterizando a los grafos split circle por subgrafos inducidos prohibidos

NINA PARDAL

Otro; Escuela de Ciencias Informáticas 2021; 2021

DC-ICC, UBA

Los grafos circle fueron definidos por Even e Itai en los 70' para resolver un problema postulado por Knuth, relacionado a colas y pilas. Ellos hallaron que el problema de Knuth era equivalente a encontrar el número cromático de un grafo circle.Existen muchas caracterizaciones de los grafos circle, pero todas son mas bien algorítmicas (i.e., dado el grafo, hay que realizarle ciertas operaciones de modo sistemático hasta reducir al grafo a una cierta cosa), y no se conocen caracterizaciones por subgrafos prohibidos para toda la clase. Es decir, que no conocemos una lista tal que, si me dan un grafo y yo me aseguro que no tiene ninguno de esa lista, entonces puedo afirmar que mi grafo es circle. Las caracterizaciones por subgrafos prohibidos suelen ser muy útiles para resolver problemas puntuales cuando estamos trabajando con una clase de grafos específica, ya sea matemática o computacionalmente.Para tratar de avanzar en esos temas se han logrado algunas caracterizaciones parciales, es decir, se ha encontrado una lista de subgrafos prohibidos cuando el grafo además de ser circle pertenece a otra clase. En la charla vamos a hablar de una de tales caracterizaciones parciales: los subgrafos prohibidos de los grafos split que también son circle.