We show that the class of finite rooted binary plane trees is a Ramsey class (with respect to topological embeddings that map leaves to leaves). That is, for all such trees P,H and every natural number k there exists a tree T such that for every k-coloring of the (topological) copies of P in T there exists a (topological) copy H' of H in T such that all copies of P in H' have the same color. When the trees are represented by the so-called rooted triple relation, the result gives rise to a Ramsey class of relational structures with respect to induced substructures.
Abstract We give an algorithm for finding the set of all rooted trees with labelled leaves having subtrees homeomorphic to each of a given set of rooted trees with labelled leaves. This type of problem arises in the study of evolutionary trees. In taxonomy and other branches of classification it is useful to know when tree-like classifications on overlapping sets of labels can be consistently combined into a parent tree. This paper considers the computation complexity of this problem. Recognizing when a consistent parent tree exists is shown to be intractable (NP-complete) for sets of unrooted trees, even when each tree in the set classifies just four labels. Consequently determining the compatibility of qualitative characters and partial binary characters is, in general, also NP-complete. However for sets of rooted trees an algorithm is described which constructs the “strict consensus tree” of all consistent parent trees (when they exist) in polynomial time. The related question of recognizing when a set of subtrees uniquely defines a parent tree is also considered, and a simple necessary and sufficient condition is described for rooted trees. We are given a set ( T ) = T 1 ,T 2 , . . .,T k of rooted binary trees, each T i leaf-labeled by a subset ( L (T_i) 1,2, . . ., n ) . If T is a tree on 1,2, . . .,n , we let ( T| L ) denote the minimal subtree of T induced by the nodes of ( L ) and all their ancestors. The consensustreeproblem asks whether there exists a tree T * such that, for every i , ( T^* | L (T_i) ) is homeomorphic to T i .