Coloraciones L(2,1)

Ponente(s): Aldo Lozano Piña, Dr. Julián Alberto Fresán Figueroa, Dra. Mika Olsen

La coloración de tipo L(2, 1) sobre una gráfica G = (V, A) es aquella que le asigna un color (un número entero n > 0) a cada nodo v de G tales que, la diferencia entre los colores de dos vértices cualesquiera vi y vj es mayor o igual que 2 si éstos son adyacentes, y mayor o igual que 1 si están al menos a un nodo de distancia. En este trabajo se expone la L(2, 1)-coloración de algunos tipos de gráficas, tales como las trayectorias, los ciclos y las ruedas, así como el número cromático de cada una de ellas y la demostración del por qué es este número. También se expone el número cromático de la gráfica de Petersen. Se da una breve introducción a lo que es el número de Grundy y cómo se obtuvo el máximo número de coloración de las trayectorias con 9 vértices y el de la gráfica de Petersen.