Sesión Matemática DiscretaCaracterización de grafos "trivially perfect" de "proper thinness" 2
Barbara Rivero
FCEyN - UBA , Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
La proper thinness de un grafo es un invariante que generaliza el concepto de grafo de intervalos propio. Todo grafo tiene un valor numérico de proper thinness, y los grafos con proper thinness igual a 1 son exactamente los grafos de intervalos propios.
Un grafo es proper $k$-thin si sus vértices pueden ordenarse de tal manera que exista una partición de los vértices en $k$ clases que satisfaga que, para cada triple de vértices $r \lt s \lt t$, tal que existe una arista entre $r$ y $t$, se cumple 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 proper thinness es el menor valor de $k$ tal que el grafo es proper $k$-thin.
En este trabajo nos enfocamos en el cálculo de la proper thinness para los grafos threshold y trivially perfect, donde los grafos threshold son una subclase de los trivially perfect. Caracterizamos los grafos trivially perfect con proper thinness 2, tanto estructuralmente como por sus subgrafos inducidos mínimos prohibidos. Por otro lado, se concluye que los grafos threshold tienen, como máximo, proper thinness igual a 2.
Trabajo en conjunto con: Eric Brandwein (FCEyN, Universidad de Buenos Aires, Argentina), Ignacio Maqueda (FCEyN, Universidad de Buenos Aires, Argentina) y Flavia Bonomo (FCEyN, Universidad de Buenos Aires, Argentina).
Referencias
[1] F. Bonomo Et al. On the thinness and proper thinness of a graph, 2020