Recovering trees from well-separated multi-state characters

AbstractRecently, by studying Z5-edge colorings of bifurcating phylogenetic trees, Semple and Steel showed that every such tree can be convexly defined by at most five characters. The investigation of the rich structure of such edge colorings led us to the definition of a set of well-separated characters on a phylogenetic tree T that covers T which we study here. In particular, we show that such a set C of characters convexly defines a bifurcating phylogenetic tree T and that, provided this cover is sparse, the so called relation graph associated to C coincides with T. As a consequence of our results, it follows that T can be reconstructed from C in polynomial time