Max-coloring Paths

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^k_{i=1} max_{v \in C_i} w(v_i)$ is minimized, where $C_1, \ldots ,C_k$ are the various color classes. For general graphs, max-coloring is as hard as the classical vertex coloring problem. Here we study the max-coloring problem for simple paths. Note that if the vertices are unweighted, this reduces to the classical vertex coloring problem and hence the solution is to use 2 colors. However for the weighted case, one can construct simple instances where using more colors turns out to be optimal.

In this talk we will see an algorithm to optimally color the given path, that runs in time $O(n + S(n))$, where $n$ is the number of vertices and $S(n)$ is the time required to sort the vertex weights. We will then proceed to see a proof of a lower bound matching this running time.

This result appears in ISAAC 2009, titled `Max-coloring paths: Tight bounds and extensions' by Kavitha Telikepalli and Juli\'an Mestre.