Skip to main content

Research Repository

Advanced Search

Identifying phylogenetic trees

Bordewich, M.; Huber, K.; Semple, C.


K. Huber

C. Semple


A central problem that arises in evolutionary biology is that of displaying partitions of subsets of a finite set X on a tree whose vertices are partially labelled with the elements of X. Such a tree is called an X-tree and, for a collection C of partitions of subsets of X, characterisations for the existence and uniqueness of an X-tree that displays C have been previously given in terms of chordal graphs. In this paper, we obtain two closely related characterisations also in terms of chordal graphs. The first describes when C identifies an X-tree, and the second describes when a compatible subset of C is of maximum size.


Bordewich, M., Huber, K., & Semple, C. (2005). Identifying phylogenetic trees. Discrete Mathematics, 300(1-3), 30-43.

Journal Article Type Article
Publication Date 2005-09
Journal Discrete mathematics.
Print ISSN 0012-365X
Publisher Elsevier
Volume 300
Issue 1-3
Pages 30-43
Keywords Phylogenetic tree; Identifying; Restricted chordal completion