Geodesic
A complete classification of the complexity of the vertex 3-colourability problem for quadruples of induced 5-vertex prohibitions
Žurnal Srednevolžskogo matematičeskogo obŝestva, Tome 22 (2020) no. 1, pp. 38-47

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

The vertex 3-colourability problem for a given graph is to check whether it is possible to split the set of its vertices into three subsets of pairwise non-adjacent vertices or not. A hereditary class of graphs is a set of simple graphs closed under isomorphism and deletion of vertices; the set of its forbidden induced subgraphs defines every such a class. For all but three the quadruples of 5-vertex forbidden induced subgraphs, we know the complexity status of the vertex 3-colourability problem. Additionally, two of these three cases are polynomially equivalent; they also polynomially reduce to the third one. In this paper, we prove that the computational complexity of the considered problem in all of the three mentioned classes is polynomial. This result contributes to the algorithmic graph theory.
Keywords: vertex 3-colourability problem, hereditary graph class
Mots-clés : polynomial-time algorithm. 
@article{SVMO_2020_22_1_a2,
     author = {D. S. Malyshev},
     title = {A complete classification of the complexity of the vertex 3-colourability problem for quadruples of induced 5-vertex prohibitions},
     journal = {\v{Z}urnal Srednevol\v{z}skogo matemati\v{c}eskogo ob\^{s}estva},
     pages = {38--47},
     publisher = {mathdoc},
     volume = {22},
     number = {1},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SVMO_2020_22_1_a2/}
}
TY  - JOUR
AU  - D. S. Malyshev
TI  - A complete classification of the complexity of the vertex 3-colourability problem for quadruples of induced 5-vertex prohibitions
JO  - Žurnal Srednevolžskogo matematičeskogo obŝestva
PY  - 2020
SP  - 38
EP  - 47
VL  - 22
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SVMO_2020_22_1_a2/
LA  - ru
ID  - SVMO_2020_22_1_a2
ER  - 
%0 Journal Article
%A D. S. Malyshev
%T A complete classification of the complexity of the vertex 3-colourability problem for quadruples of induced 5-vertex prohibitions
%J Žurnal Srednevolžskogo matematičeskogo obŝestva
%D 2020
%P 38-47
%V 22
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SVMO_2020_22_1_a2/
%G ru
%F SVMO_2020_22_1_a2
D. S. Malyshev. A complete classification of the complexity of the vertex 3-colourability problem for quadruples of induced 5-vertex prohibitions. Žurnal Srednevolžskogo matematičeskogo obŝestva, Tome 22 (2020) no. 1, pp. 38-47. http://geodesic.mathdoc.fr/item/SVMO_2020_22_1_a2/