Abstract
Given a graph G, a proper k-coloring of G is a partition c = (S i) i∈[0,k−1] of V (G) into k stable sets S 0 ,. .. , S k−1. Given a weight function w : V (G) → R + , the weight of a color S i is dened as w(i) = max v∈S i w(v) and the weight of a coloring c as w(c) = k−1 i=0 w(i). Guan and Zhu [Inf. Process. Lett., 1997] dened the weighted chromatic number of a pair (G, w), denoted by σ(G, w), as the minimum weight of a proper coloring of G. For a positive integer r, they also dened σ(G, w; r) as the minimum of w(c) among all proper r-colorings c of G. The complexity of determining σ(G, w) when G is a tree was open for almost 20 years, until Araújo et al. [SIAM J. Discrete Math., 2014] recently proved that the problem cannot be solved in time n o(log n) on n-vertex trees unless the Exponential Time Hypothesis (ETH) fails. The objective of this article is to provide hardness results for computing σ(G, w) and σ(G, w; r) when G is a tree or a forest, relying on complexity assumptions weaker than the ETH. Namely, we study the problem from the viewpoint of parameterized complexity, and we assume the weaker hypothesis FPT = W[1]. Building on the techniques of Araújo et al., we prove that when G is a forest, the decision problem of computing σ(G, w) is W[1]-hard parameterized by the size of a largest connected component of G, and that computing σ(G, w; r) is W[2]-hard parameterized by r. Our results rule out the existence of FPT algorithms for computing these invariants on trees or forests for many natural choices of the parameter.