Extremal problems for colored trees and Davenport-Schinzel sequences
Motivated by the theory of Davenport-Schinzel sequences the author asks for the maximum number \(\text{Ex}_T(P,n,l)\) of vertices of trees \(T\) fulfilling several conditions: If \(n\) is the maximum number of colors to be used and \(P\) is some given colored tree using \(k\) colors where \(k\leq l\), then \(T\) must not contain a properly 2-colored 3-star \(K_{1,3}\), each pair of vertices of \(T\) with the same color is in distance at least \(l\), and \(P\) must not occur as a refinement in \(T\) with respect to any permutation of the colors. This problem is investigated in detail for the case that \(k\) equals \(l\) and that \(P\) is a colored path. For some short paths exact results for the extremal numbers are obtained, upper bounds are given in more general cases.
- A Combinatorial Problem Connected with Differential Equations
- A linear upper bound in extremal theory of sequences
- Combinatorial aspects of Davenport-Schinzel sequences
- Efficiency of a Good But Not Linear Set Union Algorithm
- Generalized Davenport-Schinzel sequences
- Generalized Davenport-Schinzel sequences with linear upper bound
- scientific article; zbMATH DE number 427792 (Why is no real title available?)
- scientific article; zbMATH DE number 732977 (Why is no real title available?)
- scientific article; zbMATH DE number 888842 (Why is no real title available?)
- Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
- On \(abab\)-free and \(abba\)-free set partitions
- On a problem of Davenport and Schinzel
- On geometric graphs with no k pairwise parallel edges
- Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
This page was built for publication: Extremal problems for colored trees and Davenport-Schinzel sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1292853)
