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

Article

On 3-сolouring of graphs with short faces and bounded maximum vertex degree

The vertex 3-colourability problem is to verify whether it is possible to split the vertex set of a given graph into three subsets of pairwise nonadjacent vertices or not. This problem is known to be NP-complete for planar graphs of the maximum face length at most 4 (and, even, additionally, of the maximum vertex degree at most 5), and it can be solved in linear time for planar triangulations. Additionally, the vertex 3-colourability problem is NP-complete for planar graphs of the maximum vertex degree at most 4, but it can be solved in constant time for graphs of the maximum vertex degree at most 3. It would be interesting to investigate classes of planar graphs with simultaneously bounded length of faces and the maximum vertex degree and to find the threshold, for which the complexity of the vertex 3-colourability problem is changed from polynomial-time solvability to NP-completeness. In this paper, we prove NP-completeness of the vertex 3-colourability problem for planar graphs of the maximum vertex degree at most 4, whose faces are of length no more than 5.