Dr. José Cáceres. Universidad de Almería

Estado del arte en dimensión métrica de grafos

En esta charla, trataré de describir los resultados más importantes y el estado actual del trabajo que se viene realizando relativo a la dimensión métrica. Éste es un parámetro de grafos introducido en 1975 por P. Slater y que ha recibido considerable atención en los últimos años. Sus aplicaciones van desde el diseño de estrategias de resolución del Mastermind (en su versión estática), exploración de redes, verificación, navegación robótica, localización por radar o sonar, diseño de fármacos o en el problema de localizar las monedas falsas. Intentaré abarcar un panorama lo más amplio posible, mostrando, entre otras cuestiones, el aspecto computacional, la dimensión métrica de ciertas clases de grafos distinguidas, el caso de grafos infinitos, el comportamiento ante ciertas operaciones con grafos, las variantes que se han generado recientemente asiacute; como la relación entre la dimensión métrica y otros parámetros conocidos.

Dr. Alberto Márquez. Universidad de Sevilla

Coloración robusta de grafos

Dados dos grafos G y H sobre el mismo conjunto de vértices, con iacute;ndice cromático de G igual a k, una coloración robusta del grafo unión es una asignación con k+t colores tal que sobre G es una coloración y el número de aristas monocromáticas de H es mínimo. En esta charla repasamos algunas de sus aplicaciones, asiacute; como varios de los resultados recientes obtenidos sobre este problema.