Triangulating vertex colored graphs

We are interested in the class of vertex colored graphs which can be triangulated without the introduction of edges between vertices of the same color. This is related to a fundamental and longstanding problem for numerical taxonomists, called the Perfect Phylogeny problem. These problems are known to be polynomially equivalent and NP-Complete. In this paper we present a dynamic programming algorithm which can be used to determine whether a given vertex colored graph can be so triangulated, and which runs in O((n+m(k-2))^k+1) time, where the graph has n vertices, m edges, and k colors. The corresponding algorithm for the Perfect Phylogeny Problem runs in O(r^k+1k^k+1+nk²) time, where n species are defined by k characters each having r states.