Quartet compatibility and the quartet graph
A collection P of leaf-labelled trees is compatible if there exists a single leaf-labelled tree that displays each of the trees in P. Despite its difficulty, determining the compatibility of P is a fundamental task in evolutionary biology. Attractive characterizations in terms of chordal graphs have been previously given for this problem as well as for the problems of (i) determining if there is a unique tree that displays each of the trees in P, that is 'P is definitive and (ii) determining if there is a tree that displays P and has the property that every other tree that displays P is a refinement of it, that is 'P identifies a leaf-labelled tree. In this paper, we describe new characterizations of each of these problems in terms of edge colourings. Furthermore, for an arbitrary leaf-labelled tree 'T, we also determine the minimum number of 'quartets' required to identify 'T, thus correcting a previously published result.
- Engineering: Reports