A refined analysis of online path coloring in trees

Our results are on the online version of path coloring in trees where each request is a path to be colored online, and two paths that share an edge must get different colors. For each T, we come up with a hierarchical partitioning of its edges with a minimum number of parts, denoted by h(T), and design an O(h(T))-competitive online algorithm. We then use the lower bound technique of Bartal and Leonardi [1] along with a structural property of the hierarchical partitioning, to show a lower bound of Ω(h(T)/log(4h(T))) for each tree T on the competitive ratio of any deterministic online algorithm for the problem. This gives us an insight into online coloring of paths on each tree T, whereas the current tight lower bound results are known only for special trees like paths and complete binary trees.