A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
Petr A. Golovach, Matthew Johnson, Daniël Paulusma, Jian Song · Journal of Graph Theory · 2016
Abstract For a positive integer k, a k‐coloring of a graph is a mapping such that whenever . The Coloring problem is to decide, for a given G and k, whether a k‐coloring of G exists. If k is fixed (i.e., it is not part of the input), we have the decision problem k‐Coloring instead. We survey known results on the computational complexity of Coloring and k‐Coloring for graph classes that are characterized by one or two forbidden induced subgraphs. We also consider a number of variants: for example, where the problem is to extend a partial coloring, or where lists of permissible colors are given for each vertex.