L(2,1)-Coloraciones Glotonas

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

Una L(2,1)-coloración de una gráfica consiste en asignar números enteros no negativos a sus vértices, de tal manera que dos vértices adyacentes tengan asignados números enteros que difieren al menos por 2, y dos vértices que no son adyacentes pero tienen algún vecino en común tengan asignados números que difieren al menos por 1. Se busca minimizar el tamaño del número mas grande asignado a los vértices y este problema en general es muy difícil. Una algoritmo glotón es un algoritmo eficiente para encontrar una L(2,1)-coloración y podría ayudar a encontrar el número mas grande asignado, pero la pregunta del millón es: ¿qué tan mala puede ser una coloración glotona?