Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

A survey on the computational complexity of coloring graphs with forbidden subgraphs.

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.

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.

Item Type:Article
Full text:(AM) Accepted Manuscript
Download PDF
(476Kb)
Status:Peer-reviewed
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

Export:
Export
Look up in GoogleScholar