|
This article is cited in 5 scientific papers (total in 5 papers)
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
Abstract:
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.
Keywords:
$3$-colorability problem, hereditary class, computational complexity.
Received: 11.04.2018 Revised: 20.05.2018
Citation:
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
Linking options:
https://www.mathnet.ru/eng/da912 https://www.mathnet.ru/eng/da/v25/i4/p112
|
Statistics & downloads: |
Abstract page: | 211 | Full-text PDF : | 107 | References: | 24 |
|