Rainbow Turán problems for paths and forests of stars

MaRDI QIDQ510352zbMATH OpenFDO

Authors Yong-Cai Geng, Sumit K. Garg

Publication date 17 February 2017

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

Full work available at URL https://arxiv.org/abs/1609.00069, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p34

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

zbMATH Keywords

pathsstarsrainbow Turán numbers

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(17)

• Directed graphs without rainbow stars
• Lower bounds for rainbow Turan numbers of paths and other trees
• Turán numbers for hypergraph star forests
• On the rainbow planar Turán number of double stars
• The generalized rainbow Turán problem for cycles
• 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
• On the rainbow Turán number of paths
• Generalizations of the Ruzsa–Szemerédi and rainbow Turán problems for cliques
• Rainbow cycles versus rainbow paths
• Rainbow Turán Problems
• Extremal results for graphs avoiding a rainbow subgraph
• Local rainbow colorings for various graphs
• Rainbow Turán numbers of matchings and forests of hyperstars in uniform hypergraphs
• scientific article; zbMATH DE number 7771745 (Why is no real title available?)
• Graphs without a Rainbow Path of Length 3

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)