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

Article

On the Complexity of the Vertex 3-Coloring Problem for the Hereditary Graph Classes With Forbidden Subgraphs of Small Size

Journal of Applied and Industrial Mathematics. 2018. Vol. 12. No. 4. P. 759-769.

The 3-coloring problem for a given graph consists in verifying whether it is possible
 to divide the vertex set of the graph into three subsets of pairwise nonadjacent vertices. A complete
complexity classification is known for this problem for the hereditary classes defined by triples of
forbidden induced subgraphs, each on at most 5 vertices. In this article, the quadruples of forbidden
induced subgraphs is under consideration, each on at most 5 vertices. For all but three corresponding
hereditary classes, the computational status of the 3-coloring problem is determined. Considering
two of the remaining three classes, we prove their polynomial equivalence and polynomial
reducibility to the third class.