Sobre un problema de doble coloreo y dominancia en grafos

Resumen

Un vértice v de un grafo es un dominator de un conjunto S de vértices si es adyacente a todos los elementos de S distintos de v. Un dominator coloring de un grafo es un coloreo propio tal que todos los vértices son dominator de los vértices de algún color. Un total dominator coloring de un grafo es un dominator coloring sin colores de un solo vértice. El concepto de dominator coloring tuvo su origen en la década de 1970 y ha sido ampliamente estudiado así como algunas de sus variantes.

En este trabajo consideramos una variante de estos problemas donde se consideran dos coloreos del grafo tales que cada vértice es un dominator de los vértices de algún color distinto al que recibe para los dos coloreos. Estudiamos la relación de esta variante con las variantes estudiadas anteriormente, describimos algunas propiedades básicas generales y analizamos el problema en algunas clases de grafos.