Geodesic
Efficient solvability of the~weighted vertex~coloring problem for~some two hereditary graph classes
Diskretnyj analiz i issledovanie operacij, Tome 28 (2021) no. 1, pp. 15-47

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

The weighted vertex coloring problem for a given weighted graph is to minimize the number of used colors so that for each vertex the number of the colors that are assigned to this vertex is equal to its weight and the assigned sets of vertices are disjoint for any adjacent vertices. For all but four hereditary classes that are defined by two connected $5$-vertex induced prohibitions, the computational complexity is known of the weighted vertex coloring problem with unit weights. For four of the six pairwise intersections of these four classes, the solvability was proved earlier of the weighted vertex coloring problem in time polynomial in the sum of the vertex weights. Here we justify this fact for the remaining two intersections. Bibliogr. 17.
Keywords: weighted vertex coloring problem, hereditary class, computational complexity. 
@article{DA_2021_28_1_a1,
     author = {O. O. Razvenskaya and D. S. Malyshev},
     title = {Efficient solvability of the~weighted vertex~coloring problem for~some two hereditary graph classes},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {15--47},
     publisher = {mathdoc},
     volume = {28},
     number = {1},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2021_28_1_a1/}
}
TY  - JOUR
AU  - O. O. Razvenskaya
AU  - D. S. Malyshev
TI  - Efficient solvability of the~weighted vertex~coloring problem for~some two hereditary graph classes
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2021
SP  - 15
EP  - 47
VL  - 28
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2021_28_1_a1/
LA  - ru
ID  - DA_2021_28_1_a1
ER  - 
%0 Journal Article
%A O. O. Razvenskaya
%A D. S. Malyshev
%T Efficient solvability of the~weighted vertex~coloring problem for~some two hereditary graph classes
%J Diskretnyj analiz i issledovanie operacij
%D 2021
%P 15-47
%V 28
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2021_28_1_a1/
%G ru
%F DA_2021_28_1_a1
O. O. Razvenskaya; D. S. Malyshev. Efficient solvability of the~weighted vertex~coloring problem for~some two hereditary graph classes. Diskretnyj analiz i issledovanie operacij, Tome 28 (2021) no. 1, pp. 15-47. http://geodesic.mathdoc.fr/item/DA_2021_28_1_a1/