Polynomial Strategies for the 3-Coloring of a Graph

Abstract

El coloreo de un grafo es un problema de interés en el área de las ciencias de la computación debido a las muchas aplicaciones que este ofrece. El problema de coloreo de un grafo tiene varias aplicaciones en áreas como en el problema de asignación de tareas, asignación de frecuencias, planeación, etc. En el coloreo de un grafo, se asigna un color apropiado a los nodos (de forma que dos nodos adyacentes no tengan igual color), usando el menor numero posible de colores. Se presentan algunas condiciones necesarias para el 3-coloreo de un grafo de entrada, todas esas condiciones se pueden comprobar en tiempo polinomial.También se propone un patrón combinatorio apropiado para la representación del 3-coloreo de un grafo basado en sus ciclos básicos, y donde dicho patrón es codificado a través de la satisfactibilidad de una formula booleana en dos forma conjuntiva. La formula booleana es formada de acuerdo alos ciclos básicos presentes en el grafo. En este artículo se presenta una metodología para el 3-coloreo de un grafo utilizando 2-CF (dos forma conjuntiva), así como su cálculo por medio de ejemplos / Guillermo De Ita Luna, Yuridiana Alemán and Nahum Loya.