Decompositions of leaf-colored binary trees (Q1802339)

Evolutionary trees (e.g. leaf-colored binary trees) arise in biomathematics. The evaluation of different heuristics for the NP-hard most parsimonious evolutionary tree problem requires statistics on different numerical parameters of evolutionary trees having fixed pre- colored leaf-set. This research has already been done by an earlier paper of the author [Discrete Appl. Math. 41, No. 3, 245-261 (1993; see the review above)] for 2-colored trees. This paper is aimed to extend that study to multicolored trees. As a possible first step to approach the desired statistics, the author proved enumerative results on special classes of evolutionary trees with 3 or more colors. The fundamental decomposition theorems are based on Menger's theorem and its generalization, see \textit{P. L. Erdős} and \textit{L. A. Székely} [Adv. Appl. Math. 13, No. 4, 375-389 (1992; Zbl 0773.05047)].