Skip to main content

Research Repository

Advanced Search

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

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

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


Authors

P.A. Golovach

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
Public URL https://durham-repository.worktribe.com/output/1389918
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.






You might also like



Downloadable Citations