Caracterizando gráficas mediante subestructuras prohibidas

Ponente(s): César Hernández Cruz

Se dice que una propiedad P en teoría de gráficas es hereditaria si para cualquier gráfica que cumpla P, se tiene que todas sus subgráficas inducidas también cumplen P; por ejemplo, "no tener ciclos" es una propiedad hereditaria, mientras que "ser conexa" no lo es. Por definición, cualquier gráfica con un solo vértice cumple cualquier propiedad hereditaria, por lo tanto, cualquier gráfica G que no tiene la propiedad hereditaria P debe contener una subgráfica H tal que no cumpla la propiedad P, pero tal que toda subgráfica inducida de H sí la cumpla; llamamos a H una obstrucción mínima para P. Claramente, si una gráfica no contiene obstrucciones mínimas para P, ésta debe de cumplir la propiedad P: por ejemplo, las obstrucciones mínimas para la propiedad "ser bipartita" son exactamente los ciclos de longitud impar, por lo tanto, una gráfica que no contiene ciclos inducidos de longitud impar, es necesariamente bipartita. En esta ponencia revisaremos algunas familias interesantes de gráficas que pueden caracterizarse mediante un conjunto de obstrucciones mínimas fácil de de reconocer. También hablaremos sobre una forma alternativa de caracterizar propiedades hereditarias utilizando un orden parcial sobre el conjunto de vértices de una gráfica.