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). pp. 331-363.
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.
|Full text:||(AM) Accepted Manuscript|
Download PDF (476Kb)
|Publisher Web site:||https://doi.org/10.1002/jgt.22028|
|Publisher 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.|
|Date accepted:||18 January 2016|
|Date deposited:||29 March 2016|
|Date of first online publication:||02 March 2016|
|Date first made open access:||02 March 2017|
Save or Share this output
|Look up in GoogleScholar|