Por favor, use este identificador para citar o enlazar este ítem:
http://repositorio.ufc.br/handle/riufc/76242| Tipo: | Dissertação |
| Título : | Complexidade do problema de K-coloração em grafos livres de H |
| Título en inglés: | Complexity of the K-coloring problem in H-free graphs |
| Autor : | Paiva, Lúcio Carlos Pimentel |
| Tutor: | Silva, Ana Shirley Ferreira da |
| Palabras clave en portugués brasileño: | coloração;índice cromático;grafos livres de Pk;complexidade |
| Palabras clave en inglés: | coloring;chromatic index;free graphs of Pk;complexity |
| Áreas de Conocimiento - CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::MATEMATICA::MATEMATICA APLICADA::MATEMATICA DISCRETA E COMBINATORIA |
| Fecha de publicación : | 2019 |
| Citación : | PAIVA, Lúcio Carlos Pimentel. Complexidade do problema de K-coloração em grafos livres de H. 2019. 53 f. Dissertação (Mestrado Acadêmico em Matemática) – Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2019. |
| Resumen en portugués brasileño: | O problema de coloração é um dos problemas mais estudados em Teoria dos Grafos. É sabido que decidir se um grafo possui uma coloração com 3 cores é um problema NP-completo, mesmo quando se impõem restrições sobre o grafo, como por exemplo, grafos planares ou grafos linha. Um teorema conhecido, de autoria de Král et al., acerca da dificuldade do problema diz que, dados um grafo G livre de H e um inteiro k, decidir se o número cromático de G é no máximo k é polinomial quando H é um subgrafo induzido de P4 ou de P3 + K1, e é NP-completo, caso contrário. Isso motivou o estudo da dificuldade do problema para valores fixos de k. Em particular, quando H é um grafo conexo, os únicos casos ainda em aberto ocorrem quando H é um caminho. Neste trabalho, apresentamos uma revisão bibliográfica do problema. Além disso, mostramos dois dos principais resultados relacionados a grafos livres de caminhos. |
| Abstract: | The coloring problem is one of the most studied problems in Graph Theory. It is known that deciding whether a graph has a coloring with 3 colors is an NP-complete problem, even when constraints are imposed on the graph, such as flat graphs or line graphs. A well-known theorem, authored by Král et al., about the difficulty of the problem says that, given a free graph G of H and an integer k, deciding whether the chromatic number of G is at most k is polynomial when H is an induced subgraph of P4 or P3 + K1, and is NP-complete otherwise. This motivated the study of the difficulty of the problem for fixed values of k. In particular, when H is a connected graph, the only remaining open cases occur when H is a path. In this work, we present a bibliographical review of the problem. Furthermore, we show two of the main results related to path-free graphs. |
| URI : | http://repositorio.ufc.br/handle/riufc/76242 |
| ORCID del autor: | https://orcid.org/0009-0005-7843-2262 |
| Lattes del autor: | http://lattes.cnpq.br/9917016311202952 |
| ORCID del tutor: | https://orcid.org/0000-0001-8917-0564 |
| Lattes del tutor: | http://lattes.cnpq.br/2132614695901416 |
| Derechos de acceso: | Acesso Aberto |
| Aparece en las colecciones: | DMAT - Dissertações defendidas na UFC |
Ficheros en este ítem:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| 2019_dis_lcppaiva.pdf | dissertaçao lucio carlos | 542,4 kB | Adobe PDF | Visualizar/Abrir |
Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.