Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Quartet Compatibility and the Quartet Graph. | Quartet Compatibility and the Quartet Graph Stefan Griinewald1 Peter J. Humphries2 and Charles Semple2 1 CAS-MPG Partner Institute for Computational Biology Shanghai Institutes for Biological Sciences Shanghai China and Max Planck Institute for Mathematics in the Sciences Leipzig Germany stefan@ 2 Department of Mathematics and Statistics University of Canterbury Christchurch New Zealand Submitted Oct 13 2005 Accepted Aug 1 2008 Published Aug 11 2008 Mathematics Subject Classification 05C05 92B10 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. 1 Introduction Unrooted phylogenetic evolutionary trees are used in computational biology to represent the evolutionary relationships of a set X of extant species. A fundamental way in which such trees are inferred is by amalgamating a collection P of smaller phylogenetic trees on overlapping subsets of X into a single parent tree. Collectively such amalgamation The first author was supported by the Allan Wilson Centre for Molecular Ecology and Evolution. The second and third authors were supported by the New Zealand Marsden Fund. THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 R103 1 methods are known
