𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On an Extremal Problem for Colored Trees

✍ Scribed by P. Valtr

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
93 KB
Volume
20
Category
Article
ISSN
0195-6698

No coin nor oath required. For personal study only.

✦ Synopsis

Let T be a tree such that there is a proper n-coloring c of the vertices of T which, besides a technical condition, is a k b k a k -free, i.e., T contains no subdivision of a path u 1 , . . . ,

Then T has O(kn) vertices. (The technical condition requires that T contains no subdivision of a properly 2colored star K 1,3 .) This solves a problem of Klazar, and extends analogous results for generalized Davenport-Schinzel sequences.

πŸ“œ SIMILAR VOLUMES

An extremal problem on Kr-free graphs
An extremal problem on Kr-free graphs
✍ Peter Frankl; JΓ‘nos Pach πŸ“‚ Article πŸ“… 1988 πŸ› John Wiley and Sons 🌐 English βš– 183 KB πŸ‘ 2 views

Let r, t 2 2 be integers and c a constant, 0 < c 5 ( r -2 ) / ( r -1). Suppose that G is a &-free graph on n vertices in which any t distinct vertices have at most cn common neighbors. Here an asymptotically best bound is obtained for the maximal number of edges in such graphs. This solves a problem

Extremal cover times for random walks on
Extremal cover times for random walks on trees
✍ Graham Brightwell; Peter Winkler πŸ“‚ Article πŸ“… 1990 πŸ› John Wiley and Sons 🌐 English βš– 370 KB

## Abstract Let __C~Ξ½~__(__T__) denote the β€œcover time” of the tree __T__ from the vertex __v__, that is, the expected number of steps before a random walk starting at __v__ hits every vertex of __T.__ Asymptotic lower bounds for __C~Ξ½~__(__T__) (for __T__ a tree on __n__ vertices) have been obtain

An extremal problem for subdivisions ofK
An extremal problem for subdivisions ofK?5
✍ Mader, W. πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 248 KB πŸ‘ 1 views

It is proved that every graph G with G β‰₯ 2|G| -5, |G| β‰₯ 6, and girth at least 5, except the Petersen graph, contains a subdivision of K - 5 , the complete graph on five vertices minus one edge.

An extremal bandwidth problem for bipart
An extremal bandwidth problem for bipartite graphs
✍ Robert C. Brigham; Julie R. Carrington; Ronald D. Dutton; Joseph Fiedler; Richar πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 119 KB πŸ‘ 2 views
An extremal problem for H-linked graphs
An extremal problem for H-linked graphs
✍ Alexandr Kostochka; Gexin Yu πŸ“‚ Article πŸ“… 2005 πŸ› John Wiley and Sons 🌐 English βš– 167 KB πŸ‘ 1 views

## Abstract We introduce the notion of __H__‐linked graphs, where __H__ is a fixed multigraph with vertices __w__~1~,…,__w__~m~. A graph __G__ is __H__‐__linked__ if for every choice of vertices Ο…~1~,…, Ο…~m~ in __G__, there exists a subdivision of __H__ in __G__ such that Ο…~i~ is the branch vertex