Título: Caracterización estructural de los árboles de thinness propia 2
Director: Dra. Flavia Bonomo
Jurados: Dra. Verónica Becher, Dr. Min Chih Lin

Resumen:

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 < s < 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.

La tesis se desarrolló en el marco de una beca BIICC, bajo la dirección de Flavia Bonomo y con la Dra. Nina Pardal en el rol de mentora.