Rainbow Turán problems for paths and forests of stars

zbMATH Open1355.05111arXiv1609.00069MaRDI QIDQ510352FDOQ510352

Authors: Yong-Cai Geng, Sumit K. Garg 

Publication date: 17 February 2017

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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 {emph rainbow copy} of $F$, that is, a copy of $F$ all of whose edges receive a different color. This maximum, denoted by $e{x}^{\ast }(n,F)$, is the {emph rainbow Tur'an number} of $F$, and its systematic study was initiated by Keevash, Mubayi, Sudakov and Verstra"ete in 2007. We determine $e{x}^{\ast }(n,F)$ exactly when $F$ is a forest of stars, and give bounds on $e{x}^{\ast }(n,F)$ when $F$ is a path with $k$ edges, disproving a conjecture in Keevash et al.

Full work available at URL: https://arxiv.org/abs/1609.00069

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• On the rainbow Turán number of paths
• Lower bounds for rainbow Turan numbers of paths and other trees
• Rainbow cycles versus rainbow paths
• Generalized rainbow Turán problems
• The generalized rainbow Turán problem for cycles

zbMATH Keywords

pathsstarsrainbow Turán numbers

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)

Cites Work

• Title not available (Why is that?)
• On maximal paths and circuits of graphs
• Path Ramsey numbers in multicolorings
• Rainbow Turán Problems
• Turán numbers of multiple paths and equibipartite forests
• On the Turán number of forests
• Rainbow and orthogonal paths in factorizations of \(K_n\)
• Random subgraphs of properly edge-coloured complete graphs and long rainbow cycles
• Rainbow Turán problem for even cycles
• Heterochromatic paths in edge colored graphs without small cycles and heterochromatic-triangle-free graphs
• Hamilton circuits with many colours in properly edge-coloured complete graphs.
• On a problem of G. Hahn about coloured Hamiltonian paths in \(K_{2n}\)

Cited In (17)

• The generalized rainbow Turán problem for cycles
• Turán numbers for hypergraph star forests
• Generalizations of the Ruzsa–Szemerédi and rainbow Turán problems for cliques
• On the rainbow Turán number of paths
• Local rainbow colorings for various graphs
• Rainbow Turán Problems
• Title not available (Why is that?)
• On the rainbow planar Turán number of double stars
• Graphs without a Rainbow Path of Length 3
• Generalized rainbow Turán problems
• Generalized rainbow Turán numbers of odd cycles
• Rainbow Turán number of even cycles, repeated patterns and blow-ups of cycles
• Extremal results for graphs avoiding a rainbow subgraph
• Rainbow Turán numbers of matchings and forests of hyperstars in uniform hypergraphs
• Directed graphs without rainbow stars
• Lower bounds for rainbow Turan numbers of paths and other trees
• Rainbow cycles versus rainbow paths

This page was built for publication: Rainbow Turán problems for paths and forests of stars

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q510352)