Coloraciones de vértices en gráficas

Ponente(s): Narda Cordero Michel

Una gráfica G=(V(G), A(G)) es una pareja de conjuntos, el conjunto V(G) es un conjunto no vacío de objetos a los que llamamos vértices y A(G) es un conjuunto de parejas no ordenadas de vértices distintos llamadas aristas. A una función c: V(G) →{1, 2, …, k} se le conoce como una k-coloración de la gráfica G y si c satisface que c(x) ≠ c(y) siempre que {x, y} es una arista de G, decimos que la coloración c es una k-coloración propia. Al mínimo número de colores para el cual G admite una coloración propia se le llama el número cromático de G y se le denota por χ(G). Los coloraciones en grágicas y el número cromático han sido dos temas muy estudiados a lo largo de los años, tanto por su dificultad como por las aplicaciones que tienen. En esta plática veremos ejemplos de algunas de sus aplicaciones y algunos métodos para obtener coloraciones propias de una gráfica.