Quartet compatibility and the quartet graph

Abstract

A collection P of phylogenetic trees is compatible if there exists a single phylogenetic tree that displays each of the trees in P. Despite its computational difficulty, determining the compatibility of P is a fundamental task in evolutionary biology. Characterizations in terms of chordal graphs have been previously given for this problem as well as for the closely-related problems of (i) determining if P is definitive and (ii) determining if P identifies a phylogenetic tree. In this paper, we describe new characterizations of each of these problems in terms of edge colourings. Furthermore, making use of the tools that underlie these new characterizations, we also determine the minimum number of quartets required to identify an arbitrary phylogenetic tree, thus correcting a previously published result.