Geodesic
On the complexity for constructing a 3-colouring for planar graphs with short facets
Žurnal Srednevolžskogo matematičeskogo obŝestva, Tome 20 (2018) no. 2, pp. 199-205.

Voir la notice de l'article provenant de la source Math-Net.Ru

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 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. 
@article{SVMO_2018_20_2_a5,
     author = {D. V. Sirotkin},
     title = {On the complexity for constructing a 3-colouring for planar graphs with short facets},
     journal = {\v{Z}urnal Srednevol\v{z}skogo matemati\v{c}eskogo ob\^{s}estva},
     pages = {199--205},
     publisher = {mathdoc},
     volume = {20},
     number = {2},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SVMO_2018_20_2_a5/}
}
TY  - JOUR
AU  - D. V. Sirotkin
TI  - On the complexity for constructing a 3-colouring for planar graphs with short facets
JO  - Žurnal Srednevolžskogo matematičeskogo obŝestva
PY  - 2018
SP  - 199
EP  - 205
VL  - 20
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SVMO_2018_20_2_a5/
LA  - ru
ID  - SVMO_2018_20_2_a5
ER  - 
%0 Journal Article
%A D. V. Sirotkin
%T On the complexity for constructing a 3-colouring for planar graphs with short facets
%J Žurnal Srednevolžskogo matematičeskogo obŝestva
%D 2018
%P 199-205
%V 20
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SVMO_2018_20_2_a5/
%G ru
%F SVMO_2018_20_2_a5
D. V. Sirotkin. On the complexity for constructing a 3-colouring for planar graphs with short facets. Žurnal Srednevolžskogo matematičeskogo obŝestva, Tome 20 (2018) no. 2, pp. 199-205. http://geodesic.mathdoc.fr/item/SVMO_2018_20_2_a5/

[1] D. Dailey, “Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete”, Discrete Mathematics, 30:3 (1980), 289–293 | DOI | MR | Zbl

[2] R. Brooks, “On colouring the nodes of a network”, Proceedings of Cambridge Philosophical Society, Mathematical and physical sciences, 37:2 (1941), 194–197 | DOI | MR

[3] O. Aichholzer, F. Aurenhammer, T. Hackl, C. Huemer, A. Pilz, B. Vogtenhuber, “3-Colorability of pseudo-triangulations”, International Journal of Computational Geometry and Applications, 25:4 (2015), 283–298 | DOI | MR | Zbl

[4] D. Malyshev, “The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs”, Graphs and Combinatorics, 33:4 (2017), 1009–1022 | DOI | MR | Zbl