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

Article

A method of graph reduction and its applications

Discrete Mathematics and Applications. 2018. Vol. 28. No. 4. P. 249-258.
Sirotkin D., Malyshev D.

The independent set problem for a given simple graph is to determine the size of a maximal set
of its pairwise non-adjacent vertices. We propose a new way of graph reduction leading to a new proof of
the NP-completeness of the independent set problem in the class of planar graphs and to the proof of NPcompleteness of this problem in the class of planar graphs having only triangular internal facets of maximal
vertex degree 18