Número cromático de grafos de distancia exacta.

Abstract:

Se presentarán los principales resultados del paper “Chromatic numbers of exact distance graphs” (https://doi.org/10.1016/j.jctb.2018.05.007)

El grafo de distancia exacta p de un grafo G=(V,E) es el grafo con el mismo conjunto de vértices que G y entre dos vértices hay una arista si y sólo si estos vértices están a distancia exactamente p en G.

Usando la noción de números de coloreos generalizados se encontrarán cotas para el número cromático de grafos de distancia exacta p, separando los casos en que p sea impar y el caso en que es par.

Posted on Sep 26, 2022 in Seminario de Grafos, Seminars