Abstract:

In the theory of generalized Davenport-Schinzel sequences  one estimates the maximum lengths of finite sequences containing no subsequence  of a given pattern. Here we investigate a further generalization, in which the class of  sequences is extended to the class of colored trees. We determine exactly  the extremal functions associated with the properly 2-colored path of four vertices and  with the monochromatic path of any length. We prove that the extremal function of any colored path grows almost linearly (this is a characteristic feature of DS sequences). Three problems are posed.