• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
vision user

Article

The Complexity of the Vertex 3-Colorability Problem for Some Hereditary Classes Defined By 5-Vertex Forbidden Induced Subgraphs

Graphs and Combinatorics. 2017. Vol. 33. No. 4. P. 1009-1022.

We completely determine the complexity status of the vertex 3-colorability problem for the problem restricted to all hereditary classes defined by at most 3 forbidden induced subgraphs each on at most 5 vertices. We also present a complexity dichotomy for the problem and the family of all hereditary classes defined by forbidding an induced bull and any set of induced subgraphs each on at most 5 vertices.