Locally bounded k-colorings of trees

¹ CEDRIC, CNAM, Paris, France; This email address is being protected from spambots. You need JavaScript enabled to view it.
² CEDRIC, CNAM, Paris, France; This email address is being protected from spambots. You need JavaScript enabled to view it.

Received: 19 June 2007
Accepted: 28 July 2008

Abstract

Given a tree T with n vertices, we show, by using a dynamic programming approach, that the problem of finding a 3-coloring of T respecting local (i.e., associated with p prespecified subsets of vertices) color bounds can be solved in O(n^6p-1logn) time. We also show that our algorithm can be adapted to the case of k-colorings for fixed k.