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

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.