Sesión Matemática DiscretaColoreando los caminos de un árbol
Pablo De Caria Di Fonzo
CONICET/ CMaLP, Universidad Nacional de La Plata, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Es sabido que todo coloreo propio de las aristas de un grafo $G$ es equivalente a un coloreo propio de los vértices de su grafo de líneas. A su vez, los grafos de líneas pueden caracterizarse como los grafos de intersección por aristas de caminos de un árbol estrella.
Se dice que un grafo $G$ es $EPT$ si puede representarse como el grafo de intersección por aristas de una familia de caminos de un árbol $T$. De esta manera, se deduce que los grafos de líneas forman una subclase de los grafos $EPT$.
Como consecuencia de lo dicho arriba, el estudio del coloreo de los grafos $EPT$ cobra interés al poder ser visto como una generalización del problema del coloreo de aristas o coloreo de grafos de líneas.
En esta presentación comenzaremos con dicho estudio, considerando inicialmente restricciones sobre los árboles sobre los cuales los grafos $EPT$ se representan (en primer lugar, abordaremos el problema en árboles oruga) y sobre los caminos (si se pueden repetir o no). Nos interesará en particular comparar el número cromático de los grafos $EPT$ con su número clique y cuánto pueden llegar a diferir, mostrando casos en los que ambos coinciden.
Trabajo en conjunto con: María Pía Mazzoleni (CONICET/Universidad Nacional de La Plata) y María Guadalupe Payo Vidal (CONICET/Universidad Nacional de La Plata).