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

Article

О сложности построения 3-раскраски с короткими гранями

The vertex 3-colourability problem is to determine for a given graph whether one can divide its vertex set into three subsets of pairwise non-adjacent vertices. This problem is NP-complete in the class of planar graphs, but it becomes polynomial-time solvable for planar triangulations, i.e. planar graphs, all facets of which (including external) are triangles. Additionally, the problem is NP-complete for planar graphs whose vertices have degrees at most 4, but it becomes linear-time solvable for graphs whose vertices have maximal degree at most 3. So it is an interesting question to nd a threshold for lengths of facets and maximum vertex degree, for which the complexity of the vertex 3-colourability changes from polynomial-time solvability to NP-completeness. In this paper we answer this question and prove NP-completeness of the vertex 3-colourability problem in the class of planar graphs of the maximum vertex degree at most 5, whose facets are triangles and quadrangles only.