  In this paper, we investigate the $k$-path coloring problem, a variant of
vertex coloring arising in the context of integrated circuit manufacturing. In
this setting, typical industrial instances exhibit a `tree-like' structure. We
exploit this property to design an efficient algorithm for our industrial
problem: (i) on the methodological side, we show that the $k$-path coloring
problem can be solved in polynomial time on graphs with bounded treewidth and
we devise a simple polytime dynamic programming algorithm in this case (not
relying on Courcelle's celebrated theorem); and (ii) on the empirical side, we
provide computational evidences that the corresponding algorithm could be
suitable for practice, by testing our algorithm on true instances obtained from
an on-going collaboration with Mentor Graphics. We finally compare this
approach with integer programming on some pseudo-industrial instances. It
suggests that dynamic programming cannot compete with integer programming when
the tree-width is greater than three. While all our industrial instances
exhibit such a small tree-width, this is not for granted that all future
instances will also do, and this tend to advocate for integer programming
approaches.
