Abstract (EN)

A version of weighted coloring of a graph is introduced: each node υ of a graph G = (V,E) is provided with a positive integer weight w(υ) and the weight of a stable set S of G is w(S) = maxw(υ) : υ ∈ V ∩ S. A k-coloring S = (S 1, . . . , S k) of G is a partition of V into k stable sets S 1, . . . , S k and the weight of S is w(S 1) + . . . + w(S k ). The objective then is to find a coloring S = (S 1, . . . , S k ) of G such that w(S 1) + . . . + w(S k ) is minimized. Weighted node coloring is NP-hard for general graphs (as generalization of the node coloring problem). We prove here that the associated decision problems are NP-complete for bipartite graphs, for line-graphs of bipartite graphs and for split graphs. We present approximation results for general graphs. For the other families of graphs dealt, properties of optimal solutions are discussed and complexity and approximability results are presented.