### Abstract

We are interested here in the problem of determining whether we can triangulate a vertex-colored graph without introducing edges between vertices of the same color. This problem is motivated by a longstanding and 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 a lot of attention recently. In this paper we present an almost linear time algorithm for this problem in the case that the graph is three colored.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991 |

Publisher | Association for Computing Machinery |

Pages | 337-343 |

Number of pages | 7 |

ISBN (Print) | 0897913760 |

State | Published - Mar 1 1991 |

Externally published | Yes |

Event | 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991 - San Francisco, United States Duration: Jan 28 1991 → Jan 30 1991 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|

### Other

Other | 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991 |
---|---|

Country | United States |

City | San Francisco |

Period | 1/28/91 → 1/30/91 |

### ASJC Scopus subject areas

- Software
- Mathematics(all)

## Fingerprint Dive into the research topics of 'Triangulating three-colored graphs'. Together they form a unique fingerprint.

## Cite this

Kannan, S. K., & Warnow, T. J. (1991). Triangulating three-colored graphs. In

*Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991*(pp. 337-343). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). Association for Computing Machinery.