A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs. Issue 4 (2nd March 2016)

• Record Type: Journal Article
• Authors: Golovach, Petr A.; Johnson, Matthew; Paulusma, Daniël; Song, Jian
• Is Part Of: Journal of graph theory. Volume 84:Issue 4(2017)
• Page Start: 331
• Page End: 363
• Publication Date: 2016-03-02
• Subjects: graph coloring -- precoloring extension -- list coloring -- choosability -- forbidden induced subgraph; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22028
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: For a positive integer k, a k ‐ coloring of a graph G = ( V, E ) is a mapping c : V → { 1, 2, ..., k } such that c ( u ) ≠ c ( v ) whenever u v ∈ E . TheColoring 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 ofColoring 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.