Document Type

Article

Publication Date

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.

Publication Title

The Electronic Journal of Combinatorics

Volume

24

Issue

1

First Page

Paper #P1:34

Required Publisher's Statement

Authors retain the copyright of their articles.

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

Download
COinS