On the complexity of the vertex $3$-coloring problem for the hereditary graph classes with forbidden subgraphs of small size
D. V. Sirotkinab, D. S. Malyshevab
a National Research University Higher School of Economics, 25/12 Bolshaya Pecherskaya St., 603155 Nizhny Novgorod, Russia
b Lobachevsky State University of Nizhny Novgorod, 23 Gagarina Ave., 603950 Nizhny Novgorod, Russia
The $3$-coloring problem for a given graph consists in verifying whether it is possible to divide the vertex set of the graph into three subsets of pairwise nonadjacent vertices. A complete complexity classification is known for this problem for the hereditary classes defined by triples of forbidden induced subgraphs, each on at most $5$ vertices. In this article, the quadruples of forbidden induced subgraphs is under consideration, each on at most $5$ vertices. For all but three corresponding hereditary classes, the computational status of the $3$-coloring problem is determined. Considering two of the remaining three classes, we prove their polynomial equivalence and polynomial reducibility to the third class. Illustr. 4, bibliogr. 20.
$3$-colorability problem, hereditary class, computational complexity.
|Russian Science Foundation
|The authors were supported by the Russian Science Foundation (project no. 17-11-01336).
PDF file (1771 kB)
First page: PDF file
Journal of Applied and Industrial Mathematics, 2018, 12:4, 759–769
D. V. Sirotkin, D. S. Malyshev, “On the complexity of the vertex $3$-coloring problem for the hereditary graph classes with forbidden subgraphs of small size”, Diskretn. Anal. Issled. Oper., 25:4 (2018), 112–130; J. Appl. Industr. Math., 12:4 (2018), 759–769
Citation in format AMSBIB
\by D.~V.~Sirotkin, D.~S.~Malyshev
\paper On the complexity of the vertex $3$-coloring problem for the hereditary graph classes with forbidden subgraphs of small size
\jour Diskretn. Anal. Issled. Oper.
\jour J. Appl. Industr. Math.
Citing articles on Google Scholar:
Related articles on Google Scholar:
|Number of views:|