RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
 General information Latest issue Archive Impact factor Subscription Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Diskretn. Anal. Issled. Oper.: Year: Volume: Issue: Page: Find

 Diskretn. Anal. Issled. Oper., 2018, Volume 25, Number 4, Pages 112–130 (Mi da912)

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.

 Funding Agency Grant Number Russian Science Foundation 17-11-01336 The authors were supported by the Russian Science Foundation (project no. 17-11-01336).

DOI: https://doi.org/10.17377/daio.2018.25.617

Full text: PDF file (1771 kB)
First page: PDF file
References: PDF file   HTML file

English version:
Journal of Applied and Industrial Mathematics, 2018, 12:4, 759–769

Document Type: Article
UDC: 519.17
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

Citation in format AMSBIB
\Bibitem{SirMal18} \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. \yr 2018 \vol 25 \issue 4 \pages 112--130 \mathnet{http://mi.mathnet.ru/da912} \crossref{https://doi.org/10.17377/daio.2018.25.617} \elib{http://elibrary.ru/item.asp?id=36449714} \transl \jour J. Appl. Industr. Math. \yr 2018 \vol 12 \issue 4 \pages 759--769 \crossref{https://doi.org/10.1134/S1990478918040166} \scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85058139549}