Graphs without a Rainbow Path of Length 3

DOI10.1137/22M1535048MaRDI QIDQ6188520zbMATH OpenOpenAlexFDO

Authors Sebastian Babiński, A. Grzesik

Publication date 7 February 2024

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

extremal graph theoryrainbow coloringTurán-type problems

Mathematics Subject Classification ID

Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15) Enumeration in graph theory (05C30) Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Abstract: In 1959 ErdH{o}s and Gallai proved the asymptotically optimal bound for the maximum number of edges in graphs not containing a path of a fixed length. Here we study a rainbow version of their theorem, in which one considers $kgeq1$ graphs on a common set of vertices not creating a path having edges from different graphs and asks for the maximal number of edges in each graph. We prove the asymptotically optimal bound in the case of a path on three edges and any $kgeq1$.

Recommendations

• On the rainbow Turán number of paths
• Lower bounds for rainbow Turan numbers of paths and other trees
• Rainbow Turán problems for paths and forests of stars
• Extremal results for graphs avoiding a rainbow subgraph

Cites work

• A new proof of the graph removal lemma
• A rainbow version of Mantel's theorem
• Density of Gallai multigraphs
• Generalized rainbow Turán numbers of odd cycles
• Generalized rainbow Turán problems
• Lower bounds for rainbow Turan numbers of paths and other trees
• Multicolour Turán problems
• Non-monochromatic triangles in a 2-edge-coloured graph
• On a colored Turán problem of Diwan and Mubayi
• On maximal paths and circuits of graphs
• On the rainbow Turán number of paths
• On the structure of linear graphs
• Path Ramsey numbers in multicolorings
• Rainbow cycles versus rainbow paths
• Rainbow Turán number of even cycles, repeated patterns and blow-ups of cycles
• Rainbow Turán problem for even cycles
• Rainbow Turán Problems
• Rainbow Turán problems for paths and forests of stars
• The generalized rainbow Turán problem for cycles

Cited in

(4)

• Extremal results for graphs avoiding a rainbow subgraph
• Directed graphs without rainbow stars
• Directed graphs without rainbow triangles
• On rainbow Turán densities of trees

This page was built for publication: Graphs without a Rainbow Path of Length 3

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