Rooted structures in graphs

Resumen

Una transversal de una partición es un conjunto que contiene exactamente un elemento de cada miembro de la partición y nada más. Una coloración de un grafo es una partición de sus vértices en conjuntos independientes, es decir, conjuntos de vértices no adyacentes entre sí. Nosotros estudiamos el siguiente problema: dada una transversal $T$ de una coloración $\mathcal{C}$ de un grafo $G$, ¿existe alguna partición $\mathfrak{H}$ de un subconjunto de $V(G)$ en conjuntos conexos tal que $T$ sea una transversal de $\mathfrak{H}$ y cualesquiera dos conjuntos distintos de $\mathfrak{H}$ sean adyacentes?

Matthias Kriesell conjeturó que, para cualquier transversal $T$ de orden $k$ de una $k$-coloración $\mathcal{C}$ de algún grafo $G$ tal que cualquier par de clases de colores inducen un subgrafo conexo, existe tal partición $\mathfrak{H}$ con conjuntos adyacentes dos a dos. Esto demostraría la conjetura de Hadwiger para la clase de grafos óptimamente coloreables de forma única; sin embargo, el problema sigue abierto para todo $k\geq5$.

Este artículo presenta una visión general sobre esta conjetura. Expone resultados de mi tesis doctoral y los artículos relacionados, resume su relevancia con el problema planteado y discute algunos intentos fallidos.