zbMATH — the first resource for mathematics

A simple linear time algorithm for triangulating three-colored graphs. (English) Zbl 0785.68042
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.

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