Triangulating 3-Colored Graphs

Abstract

The problem of determining whether a vertex-colored graph can be triangulated without introducing edges between vertices of the same color is what is of interest here. This problem is known to be polynomially equivalent to a fundamental problem in numerical taxonomy called the perfect phylogeny problem, which is concerned with the inference of evolutionary history. This problem is also related to the problem of recognizing partial k-trees, a class of graphs that has received much attention recently. The problem in its general form is NP-complete and can be solved in $O( n^{k + 1} )$ time, where n is the number of vertices and k the number of colors. In this paper, a linear time algorithm for the case of 3-colored graphs is presented.