Sobre un problema de doble coloreo y dominancia en grafos

  • Pablo Rey Universidad Tecnológica Metropolitana
Palabras clave: coloreo de grafos, dominación 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.

Publicado
2023-07-10
Cómo citar
Rey, P. (2023). Sobre un problema de doble coloreo y dominancia en grafos. Memorias De Las JAIIO, 9(15), 163-163. Recuperado a partir de https://publicaciones.sadio.org.ar/index.php/JAIIO/article/view/672
Sección
SIIIO - Simposio Argentino de Informática Industrial e Investigación Operat