On the rainbow Turán number of paths

MaRDI QIDQ668069zbMATH OpenFDO

Authors Beka Ergemlidze, Abhishek Methuku, Ervin Győri

Publication date 5 March 2019

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

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

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

maximum number of edges

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Enumeration in graph theory (05C30) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: Let $F$ be a fixed graph. The rainbow Tur'an number of $F$ is defined as the maximum number of edges in a graph on $n$ vertices that has a proper edge-coloring with no rainbow copy of $F$ (where a rainbow copy of $F$ means a copy of $F$ all of whose edges have different colours). The systematic study of such problems was initiated by Keevash, Mubayi, Sudakov and Verstra"ete. In this paper, we show that the rainbow Tur'an number of a path with $k+1$ edges is less than $left(frac9k7+2ight)n$, improving an earlier estimate of Johnston, Palmer and Sarkar.

Review text

Summary: Let \(F\) be a fixed graph. The rainbow Turán number of \(F\) is defined as the maximum number of edges in a graph on \(n\) vertices that has a proper edge-coloring with no rainbow copy of \(F\) (i.e., a copy of \(F\) all of whose edges have different colours). The systematic study of such problems was initiated by \textit{P. Keevash} et al. [Comb. Probab. Comput. 16, No. 1, 109--126 (2007; Zbl 1119.05058)]. In this paper, we show that the rainbow Turán number of a path with \(k+1\) edges is less than \(\left(9k/7+2\right) n\), improving an earlier estimate of \textit{D. Johnston} et al. [Electron. J. Comb. 24, No. 1, Research Paper P1.34, 15 p. (2017; Zbl 1355.05111)].

Recommendations

• Rainbow Turán problems for paths and forests of stars
• Lower bounds for rainbow Turan numbers of paths and other trees
• Rainbow cycles versus rainbow paths
• Generalized rainbow Turán problems
• Rainbow Turán Problems

Cites work

• On a problem of G. Hahn about coloured Hamiltonian paths in \(K_{2n}\)
• On maximal paths and circuits of graphs
• Rainbow Turán problem for even cycles
• Rainbow Turán Problems
• Rainbow Turán problems for paths and forests of stars
• Random subgraphs of properly edge-coloured complete graphs and long rainbow cycles
• Theorems in the additive theory of numbers

Cited in

(20)

• Generalized rainbow Turán problems
• A note on rainbow saturation number of paths
• Riordan paths and derangements
• Generalized rainbow Turán numbers of odd cycles
• Rainbow Turán number of even cycles, repeated patterns and blow-ups of cycles
• Finding a monochromatic subgraph or a rainbow path
• Rainbow cycles versus rainbow paths
• The generalized rainbow Turán problem for cycles
• Rainbow Turán problems for paths and forests of stars
• Lower bounds for rainbow Turan numbers of paths and other trees
• Generalizations of the Ruzsa–Szemerédi and rainbow Turán problems for cliques
• Paths are Turán-good
• scientific article; zbMATH DE number 7771745 (Why is no real title available?)
• Rainbow Turán numbers of matchings and forests of hyperstars in uniform hypergraphs
• Graphs without a Rainbow Path of Length 3
• Improved bounds for proper rainbow saturation
• On the rainbow planar Turán number of paths
• On rainbow Turán densities of trees
• Rainbow Turán methods for trees
• Towards Graham's rearrangement conjecture via rainbow paths

This page was built for publication: On the rainbow Turán number of paths

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