On an extremal problem for colored trees (Q1279875)

The paper asks for the maximum number of vertices of trees possessing a proper \(n\)-colouring of their vertices such that they do not contain a subdivision of a properly \(n\)-colored star \(K_{1,3}\) (thus bounding the maximum degree by \(2n-2)\) or of a path \(u_1,\dots,u_{3k}\) with \(u_1, \dots, u_k, u_{2k+1}, \dots,u_{3k}\) of the same color and \(u_{k+1}, \dots, u_{2k}\) of another same color. It is shown that this maximum number is of growth order \(O(kn)\). This includes the answer to a problem posed by M. Klazar in his thesis (1995). The type of question has its origin in the theory of Davenport-Schinzel sequences (see \textit{M. Sharir} and \textit{P. K. Agarwal} [Davenport-Schinzel sequences and their geometric applications (University Press, Cambridge) (1995; Zbl 0834.68113)] for a survey).