Skip to main content
Article
Rainbow Turán Problems for Paths and Forests of Stars
The Electronic Journal of Combinatorics
  • Daniel Johnston, University of Montana, Missoula
  • Cory Palmer, University of Montana, Missoula
  • Amites Sarkar, Western Washington University
Document Type
Article
Publication Date
1-1-2017
Keywords
  • Rainbow Turán numbers,
  • Paths,
  • Stars
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.

Subjects - Topical (LCSH)
Graph theory; Graph coloring; Vertex operator algebras
Genre/Form
articles
Type
Text
Rights
Copying of this document in whole or in part is allowable only for scholarly purposes. It is understood, however, that any copying or publication of this document for commercial purposes, or for financial gain, shall not be allowed without the author’s written permission.
Language
English
Format
application/pdf
Citation Information
Rainbow Turán problems for paths and forests of stars, (Daniel Johnston, Cory Palmer, Amites Sarkar). Elec. J. Combinatorics Vol 24 (1) no. P1.34, 2017