Publication details for Professor Matthew JohnsonGolovach, P.A., Johnson, M., Paulusma, D. & Song. J. (2017). A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs. Journal of Graph Theory 84(4): 331-363.
- Publication type: Journal Article
- ISSN/ISBN: 0364-9024, 1097-0118
- DOI: 10.1002/jgt.22028
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
- View in another repository - may include full text
Author(s) from Durham
For a positive integer k, a k-coloring of a graph inline image is a mapping inline image such that inline image whenever inline image. 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.