MSC2020 05C15
A complete classification of the complexity of the vertex 3-colourability problem for quadruples of induced 5-vertex prohibitions
D. S. Malyshev1
| Annotation | 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, polynomial-time algorithm |
1Dmitry S. Malyshev, Professor, Department of Applied Mathematics and Information Science, National Research University Higher School of Economics (25/12 Bolshaya Pecherskaya St., Nizhny Novgorod 603155, Russia), Professor, Department of Algebra, Geometry and Discrete Mathematics, National Research Lobachevsky University of Nizhny Novgorod (23 Gagarina Avenue, Nizhny Novgorod, 603950, Russia), Dr.Sci. (Physics and Mathematics), ORCID: http://orcid.org/0000-0001-7529-8233, dsmalyshev@rambler.ru
Citation: D. S. Malyshev, "[A complete classification of the complexity of the vertex 3-colourability problem for quadruples of induced 5-vertex prohibitions]", Zhurnal Srednevolzhskogo matematicheskogo obshchestva,22:1 (2020) 38–47 (In Russian)
DOI 10.15507/2079-6900.22.202001.38-47
