Please use this identifier to cite or link to this item: http://www.repositorio.ufc.br/handle/riufc/40994
Title in Portuguese: Coloração acíclica
Title: Acyclic coloring
Author: Medeiros, Pedro Paulo de
Advisor(s): Araújo, Júlio César Silva
Keywords: Análise combinatória
Teoria dos grafos
Coloração de grafos
Coloração acíclica
Combinatorial analysis
Theory of graphs
Color in graphs
Acyclic staining
Issue Date: 2019
Citation: MEDEIROS, Pedro Paulo de. Coloração acíclica. 2019. 65 f. Dissertação (Mestrado Acadêmico em Matemática) - Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2019.
Abstract in Portuguese: Apresentaremos o estado da arte para uma subárea de coloração em grafos conhecida como coloração acíclica. Dado um grafo G finito, temos uma k-coloração acíclica de G quando temos uma k-coloração própria para G tal que quaisquer duas classes de cor induzem em G uma floresta, ou seja, um subgrafo acíclico. O menor inteiro positivo k tal que G admite uma k-coloração acíclica é o número cromático acíclico de G, denotado por χa(G). Acreditamos que este seja o primeiro texto a resumir o estado da arte para este problema, mesmo considerando outras línguas. Apresentamos os resultados organizados por tipo. Primeiro, apresentamos aqueles relativos à limitantes para o número cromático acíclico, referentes à coloração cíclica em vértices, em arestas e coloração acíclica por listas em vértices e arestas. Em seguida, listamos os resultados referentes à complexidade computacional do problema de determinar se é possível colorir aciclicamente um grafo G com k cores, dados um grafo G e um inteiro positivo k. Por fim, apresentamos problemas em aberto para a pesquisa futura.
Abstract: We will present the state of the art for a sub-area of ​​coloration in graphs known as acyclic coloration. Given a G fi nite graph, we have an acyclic k-coloration of G when we have a proper k-coloration for G such that any two color classes induce in G a vector, that is, an acyclic subgraph. The smallest positive integer k such that G admits an acyclic k-coloration is the acyclic chromatic number of G, denoted by χa (G). We believe that this is the first text to summarize the state of the art for this problem, even considering other languages. We present the results organized by type. First, we present those related to the limitation for the acyclic chromatic number, referring to the cyclic coloration in vertices, in edges and acyclic coloration by lists in vertices and edges. Next, we list the results concerning the computational complexity of the problem of determining if it is possible to acyclically colorize a graph G with k colors, given a graph G and a positive integer k. Finally, we present open questions for future research.
URI: http://www.repositorio.ufc.br/handle/riufc/40994
metadata.dc.type: Dissertação
Appears in Collections:DMAT - Dissertações defendidas na UFC

Files in This Item:
File Description SizeFormat 
2019_dis_ppmedeiros.pdfDissertaçao de Pedro Paulo1,18 MBAdobe PDFView/Open


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