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/