ISSN 2079-6900 (Print) 
ISSN 2587-7496 (Online)

Middle Volga Mathematical Society Journal

Download article

MSC2010 05C15

On the complexity for constructing a 3-colouring for planar graphs with short facets

D. S. Sirotkin1

Annotationhe 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.
Keywordscomputational 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: 0000-0002-2682-9867,

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)

DOI 10.15507/2079-6900.20.201802.199-205