Please use this identifier to cite or link to this item: http://repositorio.ugto.mx/handle/20.500.12059/2187
Full metadata record
DC FieldValueLanguage
dc.rights.licensehttp://creativecommons.org/licenses/by-nc-nd/4.0es_MX
dc.creatorGUILLERMO DE ITA LUNAes_MX
dc.date.accessioned2020-07-21T03:15:51Z-
dc.date.available2020-07-21T03:15:51Z-
dc.date.issued2012-03-01-
dc.identifier.urihttp://repositorio.ugto.mx/handle/20.500.12059/2187-
dc.description.abstractEl 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.es_MX
dc.language.isoengen
dc.publisherUniversidad de Guanajuatoes_MX
dc.relationhttps://doi.org/10.15174/au.2012.342-
dc.rightsinfo:eu-repo/semantics/openAccesses_MX
dc.sourceActa Universitaria: Multidisciplinary Scientific Journal. Vol. 22, No. NE-1 ENC (2012)es_MX
dc.titlePolynomial Strategies for the 3-Coloring of a Graphes_MX
dc.typeinfo:eu-repo/semantics/articlees_MX
dc.creator.idinfo:eu-repo/dai/mx/cvu/57559es_MX
dc.subject.ctiinfo:eu-repo/classification/cti/1es_MX
dc.subject.ctiinfo:eu-repo/classification/cti/1203es_MX
dc.subject.ctiinfo:eu-repo/classification/cti/3304es_MX
dc.subject.keywords3-Coloringen
dc.subject.keywords2-Conjunctive formen
dc.subject.keywordsGraph Coloringen
dc.subject.keywordsChromatic number of a graphen
dc.subject.keywords3-Coloreadoes_MX
dc.subject.keywords2-Forma conjuntivaes_MX
dc.subject.keywordsColoreo de un grafoes_MX
dc.subject.keywordsNúmeros cromáticos de un grafoes_MX
dc.type.versioninfo:eu-repo/semantics/publishedVersiones_MX
dc.creator.twoCANDY YURIDIANA ALEMAN MUÑOZes_MX
dc.creator.threeNAHUN ISRAEL LOYA MONARESes_MX
dc.creator.idtwoinfo:eu-repo/dai/mx/cvu/418302es_MX
dc.creator.idthreeinfo:eu-repo/dai/mx/cvu/418570es_MX
dc.description.abstractEnglishThe 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.en
Appears in Collections:Revista Acta Universitaria

Files in This Item:
File Description SizeFormat 
Polynomial Strategies for the 3-Coloring of a Graph.pdf400.13 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.