WEIGHTED COLORING IN TREES.

A proper coloring of a graph is a partition of its vertex set into stable sets, where each part corresponds to a color. For a vertex-weighted graph, the weight of a color is the maximum weight of its vertices. The weight of a coloring is the sum of the weights of its colors. Guan and Zhu defined the weighted chromatic number of a vertex-weighted graph G as the smallest weight of a proper coloring of G. If vertices of a graph have weight 1, its weighted chromatic number coincides with its chromatic number. Thus, the problem of computing the weighted chromatic number, a.k.a. the max coloring problem, is NP-hard in general graphs. It remains NP-hard in some graph classes as bipartite graphs. Approximation algorithms have been designed in several graph classes; in particular, there exists a polynomial-time approximation scheme for trees. Surprisingly, the time-complexity of computing this parameter in trees is still open. The exponential time hypothesis (ETH) states that 3-SAT cannot be solved in subexponential time. We show that, assuming the ETH, the best algorithm to compute the weighted chromatic number of n-node trees has time-complexity nΘ(log n). Our result mainly relies on proving that, when computing an optimal proper weighted coloring of a graph G, it is hard to combine colorings of its connected components. [ABSTRACT FROM AUTHOR]