Rainbow Turán problems for paths and forests of stars

Daniel Johnston, Cory Palmer, Amites Sarkar

Research output: Contribution to journalArticlepeer-review

12 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

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