×

Weighted node coloring: When stable sets are expensive. (English) Zbl 1022.68092

Kučera, Luděk (ed.), Graph-theoretic concepts in computer science. 28th international workshop, WG 2002, Český Krumlov, Czech Republic, June 13-15, 2002. Revised papers. Berlin: Springer. Lect. Notes Comput. Sci. 2573, 114-125 (2002).
Summary: A version of weighted coloring of a graph is introduced: each node \(v\) of a graph \(G =(V,E)\) is provided with a positive integer weight \(w(v)\) and the weight of a stable set \(S\) of \(G\) is \(w(S)= \max \{w(v): v \in V\cap S\}\). A \(k\)-coloring \({\mathcal S}= (S_1,\ldots,S_k)\) of \(G\) is a partition of \(V\) into \(k\) stable sets \(S_1,\ldots,S_k\) and the weight of \(\mathcal{S}\) is \(w(S_1)+\ldots+w(S_k)\). The objective then is to find a coloring \({\mathcal S}= (S_1,\ldots,S_k)\) of \(G\) such that \(w(S_1)+\ldots+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.
For the entire collection see [Zbl 1013.00032].

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C15 Coloring of graphs and hypergraphs
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: Link