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

Authors :: Dmitriy S. Malyshev
Source :: Discrete Mathematics. 338:1860-1865
Publication Year :: 2015
Publisher :: Elsevier BV, 2015.
Abstract: 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.

Subjects :: Discrete mathematics
Combinatorics
Structural complexity theory
Computational complexity theory
P versus NP problem
Discrete Mathematics and Combinatorics
Graph
Theoretical Computer Science
Polynomial-time reduction
Mathematics

Full Text Access

Tools