Geodesic
On the complexity of the vertex $3$-coloring problem for the hereditary graph classes with forbidden subgraphs of small size
Diskretnyj analiz i issledovanie operacij, Tome 25 (2018) no. 4, pp. 112-130

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DA_2018_25_4_a7,
     author = {D. V. Sirotkin and D. S. Malyshev},
     title = {On the complexity of the vertex $3$-coloring problem for the hereditary graph classes with forbidden subgraphs of small size},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {112--130},
     publisher = {mathdoc},
     volume = {25},
     number = {4},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2018_25_4_a7/}
}
TY  - JOUR
AU  - D. V. Sirotkin
AU  - D. S. Malyshev
TI  - On the complexity of the vertex $3$-coloring problem for the hereditary graph classes with forbidden subgraphs of small size
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2018
SP  - 112
EP  - 130
VL  - 25
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2018_25_4_a7/
LA  - ru
ID  - DA_2018_25_4_a7
ER  - 
%0 Journal Article
%A D. V. Sirotkin
%A D. S. Malyshev
%T On the complexity of the vertex $3$-coloring problem for the hereditary graph classes with forbidden subgraphs of small size
%J Diskretnyj analiz i issledovanie operacij
%D 2018
%P 112-130
%V 25
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2018_25_4_a7/
%G ru
%F DA_2018_25_4_a7
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. Diskretnyj analiz i issledovanie operacij, Tome 25 (2018) no. 4, pp. 112-130. http://geodesic.mathdoc.fr/item/DA_2018_25_4_a7/