Locally bounded k-colorings of trees
Paris, France; firstname.lastname@example.org
2 CEDRIC, CNAM, Paris, France; email@example.com
Accepted: 28 July 2008
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(n6p-1logn) time. We also show that our algorithm can be adapted to the case of k-colorings for fixed k.
Mathematics Subject Classification: 05C15 / 90C39
Key words: Bounded graph coloring / tree / dynamic programming.
© EDP Sciences, ROADEF, SMAI, 2009