MSC2010 05C15
On the complexity for constructing a 3-colouring for planar graphs with short facets
D. S. Sirotkin1
| Annotation | 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. |
|---|---|
| Keywords | 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, dmitriy.v.sirotkin@gmail.com
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
