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

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

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.

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 Problems
• Rainbow Turán problem for even cycles
• 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

(15)

• Rainbow Turán problems for paths and forests of stars
• Finding a monochromatic subgraph or a rainbow path
• The generalized rainbow Turán problem for cycles
• Generalizations of the Ruzsa–Szemerédi and rainbow Turán problems for cliques
• scientific article; zbMATH DE number 7771745 (Why is no real title available?)
• Paths are Turán-good
• 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
• A note on rainbow saturation number of paths
• Rainbow Turán numbers of matchings and forests of hyperstars in uniform hypergraphs
• Riordan paths and derangements
• Lower bounds for rainbow Turan numbers of paths and other trees
• Rainbow cycles versus 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)