A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs. Issue 4 (2nd March 2016) - Golovach, Petr A.; Johnson, Matthew; Paulusma, Daniël; Song, Jian
Abstract: For a positive integer k, a k ‐ coloring of a graph G = ( V, E ) is a mapping c : V → { 1, 2, ..., k } such that c ( u ) ≠ c ( v ) whenever u v ∈ E . TheColoring 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 ofColoring 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.