Rainbow Turán Methods for Trees

The rainbow Turán number, a natural extension of the well studied traditional Turán number, was introduced in 2007 by Keevash, Mubayi, Sudakov and Verstra\"ete. The rainbow Turán number of a graph \(H\), \(ex^{*}(n,H)\), is the largest number of edges for an \(n\) vertex graph \(G\) which can b...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2022-03
Main Authors: Bednar, Vic, Bushaw, Neal
Format: Article
Language:English
Subjects:
Binary stars
Double stars
Graph coloring
Graph theory
Upper bounds
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The rainbow Turán number, a natural extension of the well studied traditional Turán number, was introduced in 2007 by Keevash, Mubayi, Sudakov and Verstra\"ete. The rainbow Turán number of a graph \(H\), \(ex^{*}(n,H)\), is the largest number of edges for an \(n\) vertex graph \(G\) which can be properly edge colored with no rainbow \(H\) subgraph. We explore the reduction method for finding upper bounds on rainbow Turán numbers, and use this to inform results for the rainbow Turán numbers of double stars, caterpillars, and perfect binary trees. In addition, we define \(k\)-unique colorings and the related \(k\)-unique Turán numbers. We provide preliminary results on this new variant on the classic problem.
ISSN:2331-8422