On the Complexity of the Vertex 3-Coloring Problem for the Hereditary Graph Classes With Forbidden Subgraphs of Small Size
- Autores: Sirotkin D.1,2, Malyshev D.1,2
-
Afiliações:
- National Research University Higher School of Economics
- Lobachevsky State University of Nizhny Novgorod
- Edição: Volume 12, Nº 4 (2018)
- Páginas: 759-769
- Seção: Article
- URL: https://journals.rcsi.science/1990-4789/article/view/213134
- DOI: https://doi.org/10.1134/S1990478918040166
- ID: 213134
Citar
Resumo
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 atmost 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.
Palavras-chave
Sobre autores
D. Sirotkin
National Research University Higher School of Economics; Lobachevsky State University of Nizhny Novgorod
Autor responsável pela correspondência
Email: dmitriy.v.sirotkin@gmail.com
Rússia, ul. Bolshaya Pecherskaya 25/12, Nizhny Novgorod, 603155; pr. Gagarina 23, Nizhny Novgorod, 603950
D. Malyshev
National Research University Higher School of Economics; Lobachevsky State University of Nizhny Novgorod
Email: dmitriy.v.sirotkin@gmail.com
Rússia, ul. Bolshaya Pecherskaya 25/12, Nizhny Novgorod, 603155; pr. Gagarina 23, Nizhny Novgorod, 603950