Vol. 2 (2021): Proceedings of the 3rd BYMAT Conference
Artículos

Rooted structures in graphs

Samuel Mohr
Masarykova univerzita Brno
Cover for TEMat monográficos, 2 (2021): Proceedings of the 3rd BYMat Conference

Publicado 28/08/2021

Palabras clave

  • rooted minor,
  • Hadwiger’s conjecture

Cómo citar

Mohr, Samuel. «Rooted structures in graphs». En: TEMat monográficos, 2 (2021): Proceedings of the 3rd BYMAT Conference, págs. 95-98. ISSN: 2660-6003.URL: https://temat.es/monograficos/article/view/vol2-p95.

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.