On the Complexity of the Vertex 3-Coloring Problem for the Hereditary Graph Classes With Forbidden Subgraphs of Small Size
- 作者: Sirotkin D.1,2, Malyshev D.1,2
-
隶属关系:
- National Research University Higher School of Economics
- Lobachevsky State University of Nizhny Novgorod
- 期: 卷 12, 编号 4 (2018)
- 页面: 759-769
- 栏目: Article
- URL: https://journals.rcsi.science/1990-4789/article/view/213134
- DOI: https://doi.org/10.1134/S1990478918040166
- ID: 213134
如何引用文章
详细
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.
作者简介
D. Sirotkin
National Research University Higher School of Economics; Lobachevsky State University of Nizhny Novgorod
编辑信件的主要联系方式.
Email: dmitriy.v.sirotkin@gmail.com
俄罗斯联邦, 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
俄罗斯联邦, ul. Bolshaya Pecherskaya 25/12, Nizhny Novgorod, 603155; pr. Gagarina 23, Nizhny Novgorod, 603950