On an extremal problem for colored trees
type: Item
instance of: scholarly article
title: On an extremal problem for colored trees
zbMATH Open document ID: 0924.05040
author: Pavel Valtr
published in: European Journal of Combinatorics
publication date: 1999-11-10T00:00:00Z
review text: 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).
reviewed by: Gerd Wegner
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 1251355
zbMATH Keywords: tree coloring
zbMATH Keywords: maximum number of vertices
zbMATH Keywords: Davenport-Schinzel sequences
MaRDI profile type: Publication
full work available at URL: eujc.1998.0248
OpenAlex ID: W2016552975
DOI: 10.1006/EUJC.1998.0248
Recommended article: Extremal problems on detectable colorings of trees
Recommended article: Extremal problems for colored trees and Davenport-Schinzel sequences
Recommended article: Maximizing and minimizing the number of generalized colorings of trees
Recommended article: Extremal \(H\)-colorings of trees and 2-connected graphs
Recommended article: Extremal trees with respect to number of \((A, B, 2 C)\)-edge colourings
Recommended article: On the dominator colorings in trees
Recommended article: Tree-coloring problems of bounded treewidth graphs
Recommended article: Maximum colored trees in edge-colored graphs
Recommended article: Q3033784
Recommended article: Maximum properly colored trees in edge-colored graphs
description: scientific article; zbMATH DE number 1251355