Graphs without a rainbow path of length 3

Sebastian Babiński; Andrzej Grzesik

doi:10.5817/CZ.MUNI.EUROCOMB23-011

Graphs without a rainbow path of length 3

EUROCOMB’23

Sebastian Babiński Andrzej Grzesik

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-011

PDF

Abstract

In 1959 Erdős and Gallai proved the asymptotically optimal bound for the maximum number of edges in graphs not containing a path of a fixed length. We investigate a rainbow version of the theorem, in which one considers $k \geq 1$ graphs on a common set of vertices not creating a path having edges from different graphs and asks for the maximum number of edges in each graph. We prove the asymptotically optimal bound in the case of a path on three edges and any $k \geq 1$.

Pages:
82–87

References

R. Aharoni, M. DeVos, S.G.H. de la Maza, A. Montejano, R. Šámal, A rainbow version of Mantel's Theorem, Advances in Combinatorics (2020), 12pp.

D. Chakarborti, J. Kim, H. Lee, H. Liu, J. Seo, On a rainbow extremal problem for color-critical graphs, arXiv: 2204.02575 (2022).

M. DeVos, J. McDonald, A. Montejano, Non-monochromatic triangles in a 2-edge-coloured graph, Electronic Journal of Combinatoris (2019), 3-8.
https://doi.org/10.37236/8193

A. Diwan, D. Mubayi, Turán's theorem with colors, preprint, http://www.math.cmu.edu/~mubayi/papers/webturan.pdf, 2007.

P. Erdős, T. Gallai, On maximal paths and circuits of graphs, Acta Math. Hungar. 10 (1959),
https://doi.org/10.1007/BF02024498

337-356.

P. Erdős, A. Stone, On the structure of linear graphs, Bull. Amer. Math. Soc. 52 (1946), 1087-1091.
https://doi.org/10.1090/S0002-9904-1946-08715-7

R.J. Faudree, R.H. Schelp, Path Ramsey numbers in multicolorings, J. Combin. Theory Ser. B 19 (1975), 150-160.
https://doi.org/10.1016/0095-8956(75)90080-5

V. Falgas-Ravry, K. Markström, E. Räty, Rainbow variations on a theme by Mantel: extremal problems for Gallai colouring templates, arXiv: 2212.07180 (2022).

V. Falgas-Ravry, K. Markström, E. Räty, Minimum degree conditions for rainbow triangles,

arXiv: 2305.12772 (2023).

J. Fox, A new proof of the graph removal lemma, Annals of Mathematics (2011), 561-579.
https://doi.org/10.4007/annals.2011.174.1.17

P. Frankl, Graphs without rainbow triangles, arXiv: 2203.07768 (2022).

P. Frankl, E. Győri, Z. He, Z. Lv, N. Salia, C. Tompkins, K. Varga, X. Zhu, Extremal results for graphs avoiding a rainbow subgraph, arXiv: 2204.07567 (2022).

P. Keevash, M. Saks, B. Sudakov, J. Verstraëte, Multicolour Turán problems, Advances in Applied Mathematics 33 (2004), 238-262.
https://doi.org/10.1016/j.aam.2003.08.005

A. Lamaison, A. Müyesser, M. Tait, On a colored Turán problem of Diwan and Mubayi, Discrete Mathematics 345,10 (2022), 113003.
https://doi.org/10.1016/j.disc.2022.113003

C. Magnant, Density of Gallai Multigraphs, Electron. J. Comb. 22 (2015), P1.28.
https://doi.org/10.37236/4615

W. Mantel, Problem 28, Wiskundige Opgaven 10 (1907), 60-61.

P. Turán, On an extremal problem in graph theory (in Hungarian), Matematikai és Fizikai

Lapok 48 (1941), 436-452.
https://doi.org/10.1002/lipi.19410480705

Metrics