Triangulating 3-colored graphs.

*(English)*Zbl 0779.05020A 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)

##### MSC:

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 |