On the rainbow Turán number of paths

zbMATH Open1406.05045arXiv1805.04180MaRDI QIDQ668069FDOQ668069

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)

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.

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

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

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

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)

Cites Work

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

Cited In (15)

• The generalized rainbow Turán problem for cycles
• Finding a monochromatic subgraph or a rainbow path
• Rainbow Turán problems for paths and forests of stars
• Generalizations of the Ruzsa–Szemerédi and rainbow Turán problems for cliques
• Title not available (Why is that?)
• 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)