Grafos H-libres y delta-estrella reducibilidad

Ponente(s): Gustavo Antonio Sandoval Angeles, Dr. Isidoro Gitler

Un grafo G es H-libre si G no tiene a H como menor. Para cada grafo 3-conexo H con a lo más once aristas, existe una caracterización de grafos que son H-libres. También hay caracterizaciones cuando H es isomorfo a uno de los grafos cubo, pirámide u octaedro. En general, en todas estas caracterizaciones, si un grafo G es H-libre, entonces G se obtiene por k-sumas de grafos 3-conexos que no tiene a H como menor. Un grafo es reducible si al aplicar una secuencia finita de operaciones elementales se obtiene un grafo de orden menor en vértices o aristas. Un ejemplo muy estudiado de operaciones elementales son las operaciones delta-estrella (delta-wye). Un grafo G es delta-estrella reducible si se puede obtener un vértice al aplicar estas operaciones. En esta plática hablaremos de dos de nuestros resultados importantes: Si un grafo G es libre del octaedro y del grafo de Petersen, entonces G es delta-estrella reducible. Si un grafo G es libre del grafo pirámide, entonces solo una de las siguientes afirmaciones se cumple: G es delta-estrella reducible o G tiene a K_6, K_{4,4}\ e o K_{4,4}/e como menor (donde e es una arista).