Familias (de gráficas) donde la herencia es cosa fácil

Ponente(s): Fernando Esteban Contreras Mendoza

El Teorema de Wagner caracteriza a las gráficas planas como aquellas que no tienen a $K_5$ ni a $K_{3,3}$ como menores. Dicho resultado es una instancia particular del Teorema de Robertson-Seymour, el cual establece que cualquier propiedad de las gráficas que sea cerrada bajo menores se puede caracterizar mediante una familia finita de menores prohibidos. Para bien o para mal, no es posible establecer un resultado análogo al Teorema de Robertson-Seymour para familias de gráficas cerradas bajo la eliminación vértices que funcione sobre la clase de todas las gráficas, sin embargo, existen familias de gráficas sobre las cuales sí se puede establecer dicho análogo. En esta platica exploraremos una condición suficiente para que una familia de gráficas posea dicha característica, exhibiremos dos ejemplos de tales familias, y explicaremos brevemente la importancia computacional de dichas caracterizaciones por subgráficas prohibidas.