zbMATH — the first resource for mathematics

Triangulating 3-colored graphs. (English) Zbl 0779.05020
A graph is called chordal if it has no induced cycles of length four or greater. A properly colored graph \(G=(V,E)\) with coloring \(c:V\to\{1,2,\ldots,k\}\) is said to be \(c\)-triangulated if there exists a chordal graph \(G'=(V,E')\), where \(E\subset E'\) and \(c\) is a proper coloring on \(G'\). Given a graph \(G\) with a proper vertex coloring, the Triangulating Colored Graph Problem (TCG) asks if \(G\) can be \(c\)- triangulated. This problem is equivalent to a problem in evolutionary tree inference called the perfect phylogeny problem. TCG is known to be NP-complete. An \(O(n^{k+1})\) algorithm for TCG was found, where \(n\) is the number of vertices and \(k\) the number of colors. This gives an \(O(n^ 4)\) algorithm for 3-colored graphs. The main contribution of this paper is to give a linear algorithm for solving TCG on 3-colored graphs.
Reviewer: K.W.Lih (Nankang)

05C15 Coloring of graphs and hypergraphs
05C05 Trees
68R10 Graph theory (including graph drawing) in computer science
92D15 Problems related to evolution
05C75 Structural characterization of families of graphs
68W10 Parallel algorithms in computer science
92D10 Genetics and epigenetics
Full Text: DOI