On the complexity for constructing a 3-colouring for planar graphs with short facets
D. S. Sirotkin1
|he 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 find 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.
|computational complexity, vertex 3-colourability problem, planar graph
1Dmitry V. Sirotkin, laboratory assistant, Department of Algebra, Geometry and Discrete Mathematics, National Research Lobachevsky University of Nizhny Novgorod (23 Gagarina avenue, Nizhny Novgorod, 603950, Russia), without academic degree, ORCID: http://orcid.org/ 0000-0002-2682-9867, firstname.lastname@example.org
Citation: D. S. Sirotkin, "[On the complexity for constructing a 3-colouring for planar graphs with short facets]", Zhurnal Srednevolzhskogo matematicheskogo obshchestva,20:2 (2018) 199–205 (In Russian)