A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs

摘要

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) not equal c(v) whenever uv is an element of E. 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. (C) 2016 Wiley Periodicals, Inc.