Max-coloring paths: tight bounds and extensions

The max-coloring problem is to compute a legal coloring of the vertices of a graph G=(V,E) with vertex weights w such that $sum_{i=1}^{k}max_{vin C_{i}}w(v_{i})$ is minimized, where C ₁,??,C _k are the various color classes. For general graphs, max-coloring is as hard as the classical vertex coloring problem, a special case of the former where vertices have unit weight. In fact, in some cases it can even be harder: for example, no polynomial time algorithm is known for max-coloring trees. In this paper we consider the problem of max-coloring paths and its generalization, max-coloring skinny trees, a broad class of trees that includes paths and spiders. For these graphs, we show that max-coloring can be solved in time O(|V|+time for sorting the vertex weights). When vertex weights are real numbers, we show a matching lower bound of ??(|V|log?|V|) in the algebraic computation tree model.