Estudiando las coloraciones L(2,1) a través de algoritmos glotones

Ponente(s): Julian Alberto Fresan Figueroa, Diego Gonzalez Moreno, Nahid Javier Nol, Mika Olsen

Las coloraciones $L(2,1)$ de una gráfica asignan enteros no negativos a sus vértices de manera que vértices adyacentes reciben colores que difieren al menos en dos unidades, mientras que vértices a distancia dos reciben colores distintos. Estas coloraciones surgieron originalmente en problemas de asignación de frecuencias y, desde entonces, han dado lugar a distintos problemas y parámetros interesantes. En esta charla veremos las coloraciones $L(2,1)$ desde la perspectiva de los algoritmos glotones. En particular, estudiaremos una versión del número de Grundy para este tipo de coloraciones, que aparece al preguntarnos qué puede pasar cuando coloreamos los vértices de manera glotona y cambiamos el orden en que los procesamos. La idea es entender qué tan malas pueden llegar a ser estas coloraciones respecto a una óptima.