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






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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
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

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}


Linking options:
  • http://mi.mathnet.ru/eng/da912
  • http://mi.mathnet.ru/eng/da/v25/i4/p112

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Дискретный анализ и исследование операций
    Number of views:
    This page:25
    References:4

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019