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

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

doi:10.1002/jgt.22028

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

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

Authors

P.A. Golovach

Professor Matthew Johnson matthew.johnson2@durham.ac.uk
Head Of Department

Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor

J. Song.

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
Related Public URLs	http://arxiv.org/abs/1407.1482

Files

Accepted Journal Article (487 Kb)
PDF

Copyright Statement
This is the accepted version of the following article: Golovach, P.A. and Johnson, M. and Paulusma, D. and Song, J. (2017) 'A survey on the computational complexity of coloring graphs with forbidden subgraphs.', Journal of graph theory, 84(4): 331-363, which has been published in final form at https://doi.org/10.1002/jgt.22028. This article may be used for non-commercial purposes in accordance With Wiley Terms and Conditions for self-archiving.