Cambios de colores buenos y no tan buenos en gráficas aristas-coloreadas

Ponente(s): Felipe Hernández Lorenzana, Hortensia Galeana Sánchez, María del Rocío Sánchez López

Sea H una gráfica posiblemente con lazos y G una gráfica simple. Decimos que una gráfica G es una gráfica H-coloreada cuando a cada arista de G le asignamos un vértice de H como un color. Un ciclo W en una gráfica H-coloreada G es un H-ciclo si y sólo si los colores de aristas consecutivas en W son vértices adyacentes en H, incluyendo la primera y última arista de W. De este modo, H determina que transiciones de colores están permitidas en G. En esta plática se exhibirán condiciones suficientes para la existencia de H-ciclos de cierta longitud en gráficas H-coloreadas.