On a rainbow extremal problem for color-critical graphs

Abstract

There has been extensive studies on the following question: given $k$ graphs $G_1,\dots ,G_k$ over a common vertex set of size $n$, what conditions on $G_i$ ensures a `colorful' copy of $H$, i.e., a copy of $H$ containing at most one edge from each $G_i$? A lower bound on ${\sum }_{i\in [k]}e(G_i)$ enforcing a colorful copy of a given graph $H$ was considered by Keevash, Saks, Sudakov, and Verstraëte. They defined ${\mathrm{ex}}_k(n,H)$ to be the maximum total number of edges of the graphs $G_1,\dots ,G_k$ on a common vertex set of size $n$ having no colorful copy of $H$. They completely determined ${\mathrm{ex}}_k(n,K_r)$ for large $n$ by showing that, depending on the value of $k$, one of the two natural constructions is always the extremal construction. Moreover, they conjectured the same holds for every color-critical graphs and proved it for 3-color-critical graphs. We prove their conjecture for 4-color-critical graphs and for almost all $r$-color-critical graphs when $r>4$. Moreover, we show that for every non-color-critical non-bipartite graphs, none of the two natural constructions is extremal for certain values of $k$. This answers a question of Keevash, Saks, Sudakov, and Verstraëte.

References in corpus (1)

• On a rainbow extremal problem for color-critical graphs

Cited by in corpus (2)

• On a rainbow extremal problem for color-critical graphs
• On the multicolor Turán conjecture for color-critical graphs