摘要：El coloreo de un grafo es un problema de interés en el área de las ciencias de la computacióndebido 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 grafobasado 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 a los 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.
其他摘要：The coloring of a graph is a problem of interest in the area of computer science due to the many applications it offers. The graph coloring problem has many utilities in areas like scheduling problems, frequency allocation, planning, etc. In the coloring of a graph, we want to color the nodes properly with the smallest possible number of colors. We present some necessary conditions for the 3-coloring of an input graph. All of those conditions can be checked in polynomial time. We also propose an appropriate combinatorial pattern representing proper 3-coloring of a graph based in its basic cycles, and where such pattern is codified via satisfy assignments of a two conjunctive Boolean formula. The Boolean formula is formed according to the basic cycles appearing in the graph. This paper shows the methodology for 3-coloring of a graph using 2-CF (Conjunctive form), as well as by several examples illustrate the calculation of it.
关键词：3-coloring; 2-Conjunctive Form; Graph Col- oring;Chromatic Number of a Graph;3-coloreado; 2-Forma conjuntiva; coloreo de un grafo; números cromáticos de un grafo
