aSchool of Computing, University of Leeds, Leeds LS2 9JT, UK
bSchool of Computing Sciences, University of East Anglia, Norwich, NR4 7TJ, UK
cDepartment of Mathematics and Statistics, University of Canterbury, Christchurch, New Zealand
Abstract:
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 of partitions of subsets of X, characterisations for the existence and uniqueness of an X-tree that displays 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 identifies an X-tree, and the second describes when a compatible subset of is of maximum size.