Moviéndose entre las ramas de dos árboles

Ponente(s): Leonardo Ignacio Martínez Sandoval

Esta es una plática amigable sobre un problema interesante en teoría de gráficas y sus generalizaciones. Si $G$ es una gráfica, podemos hacer su gráfica de árboles $A_G$ poniendo un vértice por cada árbol generador que tenga, y una arista entre dos de estos vértices si los árboles difieren en un intercambio simétrico (se puede quitar una arista y poner otra para llegar de uno a otro). Cuando $G$ se puede pensar como la unión de dos árboles generadores, podemos definir otra gráfica: la de árboles-coárboles $C_G$. Ahora hay un vértice por cada árbol generador tal que sus aristas complementarias también son un árbol generador. Las aristas de $C_G$ se definen igual que las de $A_G$. Así, $C_G$ es una subgráfica de $A_G$. Se sabe que $A_G$ cumple muchas propiedades bonitas en términos del diámetro y de distancias. ¿Será que $C_G$ también las tiene? En esta plática hablaremos de este problema, de algunas cosas que se saben de $C_G$, de variantes y, si tenemos tiempo, de generalizaciones de estos fenómenos en teoría de matroides.