Please use this identifier to cite or link to this item:
http://repositorio.ufc.br/handle/riufc/40994| Type: | Dissertação |
| Title: | Coloração acíclica |
| Title in English: | Acyclic coloring |
| Authors: | Medeiros, Pedro Paulo de |
| Advisor: | 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 Brazilian 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 |
| Appears in Collections: | DMAT - Dissertações defendidas na UFC |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| 2019_dis_ppmedeiros.pdf | Dissertaçao de Pedro Paulo | 1,18 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.