Sesión Matemática DiscretaÁrboles de thinness propia 2
Ignacio Maqueda
CONICET-UBA, Instituto de Ciencias de la Computación, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
La thinness propia de un grafo es un invariante que generaliza a los grafos de intervalos propios. Todo grafo tiene un valor numérico de thinness propia y los grafos con thinness propia 1 coinciden con los grafos de intervalos propios.
Un grafo es $k$-thin propio si sus vértices pueden ordenarse de manera que exista una partición de los vértices en $k$ clases cumpliendo que para cada tripla de vértices $r \lt s \lt t$, tales que existe una arista entre $r$ y $t$, se cumplen que si $r$ y $s$ pertenecen a la misma clase, entonces existe una arista entre $s$ y $t$, y si $s$ y $t$ pertenecen a la misma clase, entonces existe una arista entre $r$ y $s$. La thinness propia de un grafo es el menor valor de $k$ tal que el grafo sea $k$-thin propio.
En este trabajo nos enfocamos en el cálculo de la thinness propia para los árboles. Caracterizamos los árboles de thinness propia 2, tanto estructuralmente como por sus subgrafos inducidos minimales prohibidos.
También mostramos por qué los resultados obtenidos para árboles de thinness propia 2 no pueden ser generalizados a árboles de thinness propia 3.
Trabajo en conjunto con: Flavia Bonomo-Braberman (CONICET-UBA, Instituto de Ciencias de la Computación) y Nina Pardal (University of Huddersfield).