Abstract:
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.
Citation:
O. O. Razvenskaya, D. S. Malyshev, “Efficient solvability of the weighted vertex coloring problem for some two hereditary graph classes”, Diskretn. Anal. Issled. Oper., 28:1 (2021), 15–47; J. Appl. Industr. Math., 15:1 (2021), 97–117
This publication is cited in the following 1 articles:
D. S. Malyshev, O. I. Duginov, “A complete complexity dichotomy of the edge-coloring problem for all sets of 8-edge forbidden subgraphs”, J. Appl. Industr. Math., 17:4 (2023), 791–801