Geodesic
Efficient solvability of the weighted vertex coloring problem for some hereditary class of~graphs with $5$-vertex prohibitions
Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 3, pp. 71-87

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

We consider the problem of minimizing the number of colors in the colorings of the vertices of a given graph so that, to each vertex there is assigned some set of colors whose number is equal to the given weight of the vertex; and adjacent vertices receive disjoint sets. For all hereditary classes defined by a pair of forbidden induced connected subgraphs on $5$ vertices but four cases, the computational complexity of the weighted vertex coloring problem with unit weights is known. We prove the polynomial solvability on the sum of the vertex weights for this problem and the intersection of two of the four open cases. We hope that our result will be helpful in resolving the computational complexity of the weighted vertex coloring problem in the above-mentioned forbidden subgraphs. Illustr. 1, bibliogr. 18.
Keywords: weighted vertex coloring problem, hereditary class, computational complexity. 
@article{DA_2020_27_3_a3,
     author = {D. V. Gribanov and D. S. Malyshev and D. B. Mokeev},
     title = {Efficient solvability of the weighted vertex coloring problem for some hereditary class of~graphs with $5$-vertex prohibitions},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {71--87},
     publisher = {mathdoc},
     volume = {27},
     number = {3},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2020_27_3_a3/}
}
TY  - JOUR
AU  - D. V. Gribanov
AU  - D. S. Malyshev
AU  - D. B. Mokeev
TI  - Efficient solvability of the weighted vertex coloring problem for some hereditary class of~graphs with $5$-vertex prohibitions
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2020
SP  - 71
EP  - 87
VL  - 27
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2020_27_3_a3/
LA  - ru
ID  - DA_2020_27_3_a3
ER  - 
%0 Journal Article
%A D. V. Gribanov
%A D. S. Malyshev
%A D. B. Mokeev
%T Efficient solvability of the weighted vertex coloring problem for some hereditary class of~graphs with $5$-vertex prohibitions
%J Diskretnyj analiz i issledovanie operacij
%D 2020
%P 71-87
%V 27
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2020_27_3_a3/
%G ru
%F DA_2020_27_3_a3
D. V. Gribanov; D. S. Malyshev; D. B. Mokeev. Efficient solvability of the weighted vertex coloring problem for some hereditary class of~graphs with $5$-vertex prohibitions. Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 3, pp. 71-87. http://geodesic.mathdoc.fr/item/DA_2020_27_3_a3/