The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs

摘要

We completely determine the complexity status of the 3-colorability problem for hereditary graph classes defined by two forbidden induced subgraphs with at most five vertices. (C) 2015 Elsevier B.V. All rights reserved.