Colored unavoidable patterns and balanceable graphs

Abstract

We study a Turán-type problem on edge-colored complete graphs. We show that for any $r$ and $t$, any sufficiently large $r$-edge-colored complete graph on $n$ vertices with $\Omega (n^{2-1/t{r}^r})$ edges in each color contains a member from certain finite family ${\mathcal{F}}_t^r$ of $r$-edge-colored complete graphs. We conjecture that $\Omega (n^{2-1/t})$ edges in each color are sufficient to find a member from ${\mathcal{F}}_t^r$. A result of Girão and Narayanan confirms this conjecture when $r=2$. Next, we study a related problem where the corresponding Turán threshold is linear. We call an edge-coloring of a path $P_{rk}$ balanced if each color appears $k$ times in the coloring. We show that any $3$-edge-coloring of a large complete graph with $kn+o(n)$ edges in each color contains a balanced $P_{3k}$. This is tight up to a constant factor of $2$. For more colors, the problem becomes surprisingly more delicate. Already for $r=7$, we show that even $n^{2-o(1)}$ edges from each color does not guarantee existence of a balanced $P_{7k}$.

17 pages, 1 figure

References in corpus (3)

• On the balanceability of some graph classes
• A rainbow version of Mantel's Theorem
• The balancing number and list balancing number of some graph classes

Cited by in corpus (2)

• On the balanceability of some graph classes
• The balancing number and list balancing number of some graph classes