Title of article
On an Extremal Problem for Colored Trees
Author/Authors
Valtr، نويسنده , , P.، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 1999
Pages
7
From page
115
To page
121
Abstract
LetTbe a tree such that there is a propern-coloringcof the vertices ofTwhich, besides a technical condition, isakbkak-free, i.e.,Tcontains no subdivision of a pathu1,…,u3ksuch thatc(u1) = … = c(uk) = c(u2k + 1) = … = c(u3k) ≠ c(uk + 1) = … = c(u2k). ThenThasO(kn) vertices. (The technical condition requires thatTcontains no subdivision of a properly 2-colored starK1,3.) This solves a problem of Klazar, and extends analogous results for generalized Davenport–Schinzel sequences.
Journal title
European Journal of Combinatorics
Serial Year
1999
Journal title
European Journal of Combinatorics
Record number
1545730
Link To Document