Rainbow Turán problems for paths and forests of stars

Research output: Contribution to journalArticlepeer-review

16 Scopus citations

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 languageEnglish
Article number#P1.34
JournalElectronic Journal of Combinatorics
Volume24
Issue number1
DOIs
StatePublished - 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

    Fingerprint

    Dive into the research topics of 'Rainbow Turán problems for paths and forests of stars'. Together they form a unique fingerprint.

    Cite this