Complexidade do problema de K-coloração em grafos livres de H

• Ano de defesa: 2019
• Autor(a) principal: Paiva, Lúcio Carlos Pimentel
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Palavras-chave em Português: coloração; índice cromático; grafos livres de Pk; complexidade; coloring; chromatic index; free graphs of Pk; complexity; CNPQ::CIENCIAS EXATAS E DA TERRA::MATEMATICA::MATEMATICA APLICADA::MATEMATICA DISCRETA E COMBINATORIA
• Link de acesso: http://repositorio.ufc.br/handle/riufc/76242

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.