Coloración de Gráficas

Ponente(s): Yurisel Salmerón Campos

En esta pl ́atica hablaremos de sobre coloraci ́on de v ́ertices de una gr ́afica y mostraremos un algoritmo que nos permite hallar el número de coloraciones de dicha gráfica para lo cual deifiniremos conceptos necesarios como bipartición matríz de adyacencia e incidencia, color-partición, número cromático y polinomio cromático de una gráfica. El algoritmo plateado se basa en la construccui ́on de nuevas gráficas a partir de una gráfica inical, las cuáles tienen menos complejidad de trabajar.