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

Golovach, P.A.; Johnson, M.; Paulusma, D.; Song., J.

Abstract

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.

Citation

Golovach, P., 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. https://doi.org/10.1002/jgt.22028

• Journal Article Type: Article
• Acceptance Date: Jan 18, 2016
• Online Publication Date: Mar 2, 2016
• Publication Date: Apr 1, 2017
• Deposit Date: Mar 4, 2016
• Publicly Available Date: Mar 2, 2017
• Journal: Journal of Graph Theory
• Print ISSN: 0364-9024
• Electronic ISSN: 1097-0118
• Publisher: Wiley
• Peer Reviewed: Peer Reviewed
• Volume: 84
• Issue: 4
• Pages: 331-363
• DOI: https://doi.org/10.1002/jgt.22028
• Public URL: https://durham-repository.worktribe.com/output/1389918
• Related Public URLs: http://arxiv.org/abs/1407.1482