Weighted Coloring in Trees
Júlio Aráujo, Nicolas Nisse, Stéphane Pérennès · SIAM Journal on Discrete Mathematics · 2014
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^{\Theta(\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.