Abstract
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 ex*(n, F), is the rainbow Turán number of F, and its systematic study was initiated by Keevash, Mubayi, Sudakov and Verstraëte [Combinatorics, Probability and Computing 16 (2007)]. We determine ex*(n, F) exactly when F is a forest of stars, and give bounds on ex*(n, F) when F is a path with l edges, disproving a conjecture in the aforementioned paper for l = 4.
| Original language | English |
|---|---|
| Article number | #P1.34 |
| Journal | Electronic Journal of Combinatorics |
| Volume | 24 |
| Issue number | 1 |
| DOIs | |
| State | Published - Feb 17 2017 |
Funding
Research supported by University of Montana University Grant Program, grant no. M25364
| Funder number |
|---|
| M25364 |
Keywords
- Paths
- Rainbow Turán numbers
- Stars