Coloraciones (2,1) Grundy

Ponente(s): Nahid Yelene Javier Nol, Julián Fresán Figueroa, Diego Gónzalez Moreno y Mika Olsen

En los primeros años de los noventas Jerrold Griggs y Roger Yeh introdujeron una coloración en la cual los colores asignados a los vértices de una gráfica G son enteros no negativos, tales asignaciones no solo dependen de que los vértices sean adyacentes o no sino también de que vértices adyacentes tengan asignados números que difieren en dos y así se tiene la definición de las L(2, 1)-coloraciones. El span de una L(2, 1)-coloración es la diferencia entre el mayor número asignado y el menor número asignado. Uno de los algoritmos que es eficiente para encontrar este tipo de coloraciones es el algoritmo greedy. Además, de que puede ayudar a encontrar el mayor número asignado, lo cual nos da el mayor span de una L(2, 1)-coloración y esto es exactamente la definición del número L(2, 1)-Grundy de una gráfica. En esta charla hablaremos sobre algunos resultados del número L(2, 1)-Grundy de gráficas particulares.