Coloraciones localizadoras en gráficas

Ponente(s): Narda Cordero Michel

Las coloraciones localizadoras fueron introducidas por Chartrand et al. (2002) al combinar dos conceptos ya conocidos, las coloraciones propias de vértices en gráficas y los conjuntos localizadores. El objetivo de las coloraciones localizadoras es obtener una coloración propia de los vértices de una gráfica en la que cada vértice pueda ser identificado de manera única de acuerdo a la distancias de este a cada uno de los colores utilizados. Dada una gráfica G = (V, A). Una k-coloración propia de los vértices de G es una función α : V → {1, 2, . . . , k} que asigna colores distintos a vértices adyacentes. La distancia de un vértice a un conjunto S ⊆ V se define como d(v, S) = min{d(v, u) : u ∈ S}, donde d(v, u) denota la distancia usual entre vértices en la gráfica. Sea Ci = {v ∈ V : α(v) = i} para cada i ∈ {1, 2, . . . , k} y tomemos la ordenación (C1,C2, . . . ,Ck). Definimos el código de color de v como el vector: c_α(v) = (d(v,C1), d(v,C2), . . . , d(v,Ck)). Una k-coloración propia α de G es una coloración localizadora si para todo par de vértices distintos, u y v, se cumple que c_α(u) es distinto de c_α(v). En esta plática veremos coloraciones localizadoras para algunas familias de gráficas.