Rainbow Turán number of clique subdivisions
Preprint
Abstract
We show that for any integer $t\geq 2$, every properly edge-coloured graph on $n$ vertices with more than $n^{1+o(1)}$ edges contains a rainbow subdivision of $K_t$. Note that this bound on the number of edges is sharp up to the $o(1)$ error term. This is a rainbow analogue of some classical results on clique subdivisions and extends some results on rainbow Tur\'an numbers. Our method relies on the framework introduced by Sudakov and Tomon[2020] which we adapt to find robust expanders in the coloured setting.
Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Rainbow Cycles in Properly Edge-Colored GraphsCombinatorica, 2024
- Rainbow clique subdivisionsEuropean Journal of Combinatorics, 2023
- Small complete minors above the extremal edge densityCombinatorica, 2015
- Small minors in dense graphsEuropean Journal of Combinatorics, 2012
- Compact topological minors in graphsJournal of Graph Theory, 2010
- Graph Colouring and the Probabilistic Method2002
- The Extremal Function for Complete MinorsJournal of Combinatorial Theory, Series B, 2001
- Small topological complete subgraphs of “dense” graphsCombinatorica, 1988
- Lower bound of the hadwiger number of graphs by their average degreeCombinatorica, 1984
- Homomorphieeigenschaften und mittlere Kantendichte von GraphenMathematische Annalen, 1967