Rainbow Turán problems for paths and forests of stars (Q510352)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Rainbow Turán problems for paths and forests of stars |
scientific article |
Statements
Rainbow Turán problems for paths and forests of stars (English)
0 references
17 February 2017
0 references
Summary: For a fixed graph \(F\), we would like to determine the maximum number of edges in a properly edge-colored graph on \(n\) vertices which does not contain a rainbow copy of \(F\), that is, a copy of \(F\) all of whose edges receive a different color. This maximum, denoted by \(\mathrm{ex}^\ast(n,F)\), is the rainbow Turán number of \(F\), and its systematic study was initiated by \textit{P. Keevash} et al. [Comb. Probab. Comput. 16, No. 1, 109--126 (2007; Zbl 1119.05058)]. We determine \(\mathrm{ex}^\ast(n,F)\) exactly when \(F\) is a forest of stars, and give bounds on \(\mathrm{ex}^\ast(n,F)\) when \(F\) is a path with \(l\) edges, disproving a conjecture in the aforementioned paper for \(l=4\).
0 references
rainbow Turán numbers
0 references
paths
0 references
stars
0 references
0 references