Grünewald, Stefan; Humphries, Peter J.; Semple, Charles

Quartet compatibility and the quartet graph

Electron. J. Comb. 15(1), Research Paper R103, 27 p. (2008)


Summary: 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.

Mathematics Subject Classification

05C05, 92B10