Please use this identifier to cite or link to this item:
http://repositorio.ugto.mx/handle/20.500.12059/2187
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.rights.license | http://creativecommons.org/licenses/by-nc-nd/4.0 | es_MX |
dc.creator | GUILLERMO DE ITA LUNA | es_MX |
dc.date.accessioned | 2020-07-21T03:15:51Z | - |
dc.date.available | 2020-07-21T03:15:51Z | - |
dc.date.issued | 2012-03-01 | - |
dc.identifier.uri | http://repositorio.ugto.mx/handle/20.500.12059/2187 | - |
dc.description.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. | es_MX |
dc.language.iso | eng | en |
dc.publisher | Universidad de Guanajuato | es_MX |
dc.relation | https://doi.org/10.15174/au.2012.342 | - |
dc.rights | info:eu-repo/semantics/openAccess | es_MX |
dc.source | Acta Universitaria: Multidisciplinary Scientific Journal. Vol. 22, No. NE-1 ENC (2012) | es_MX |
dc.title | Polynomial Strategies for the 3-Coloring of a Graph | es_MX |
dc.type | info:eu-repo/semantics/article | es_MX |
dc.creator.id | info:eu-repo/dai/mx/cvu/57559 | es_MX |
dc.subject.cti | info:eu-repo/classification/cti/1 | es_MX |
dc.subject.cti | info:eu-repo/classification/cti/1203 | es_MX |
dc.subject.cti | info:eu-repo/classification/cti/3304 | es_MX |
dc.subject.keywords | 3-Coloring | en |
dc.subject.keywords | 2-Conjunctive form | en |
dc.subject.keywords | Graph Coloring | en |
dc.subject.keywords | Chromatic number of a graph | en |
dc.subject.keywords | 3-Coloreado | es_MX |
dc.subject.keywords | 2-Forma conjuntiva | es_MX |
dc.subject.keywords | Coloreo de un grafo | es_MX |
dc.subject.keywords | Números cromáticos de un grafo | es_MX |
dc.type.version | info:eu-repo/semantics/publishedVersion | es_MX |
dc.creator.two | CANDY YURIDIANA ALEMAN MUÑOZ | es_MX |
dc.creator.three | NAHUN ISRAEL LOYA MONARES | es_MX |
dc.creator.idtwo | info:eu-repo/dai/mx/cvu/418302 | es_MX |
dc.creator.idthree | info:eu-repo/dai/mx/cvu/418570 | es_MX |
dc.description.abstractEnglish | 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. | en |
Appears in Collections: | Revista Acta Universitaria |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Polynomial Strategies for the 3-Coloring of a Graph.pdf | 400.13 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.