A simple linear time algorithm for triangulating three-colored graphs

In this paper we consider the problem of determining whether a given coloredgraph can be triangulated, such that no edges between vertices of the same color are added. This problem originated from the perfect phylogeny problem from molecular biology and is strongly related with the problem of recognizing partial k-trees. In this paper we give asimplelineartimealgorithm that solves the problem when there are three colors. We do this by first giving a complete structural characterization of the class of partial two-trees.