A simple linear time algorithm for triangulating three-colored graphs. (English) Zbl 0785.68042

Bodlaender, Hans L.; Kloks, Ton

J. Algorithms 15, No. 1, 160-172 (1993).

Summary: We consider the problem of determining whether a given colored graph 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. We give a simple linear time algorithm 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.

MSC:

68Q25	Analysis of algorithms and problem complexity
68R10	Graph theory (including graph drawing) in computer science
05C15	Coloring of graphs and hypergraphs

Keywords:

triangulation; \(NP\)-complete; partial \(k\)-trees; colored graph; perfect phylogeny problem