Speaker
Description
We study a natural generalization of the well-studied Tur\'an problems, known as multicolor Tur\'an problems, which was first introduced and nurtured by Keevash, Saks, Sudakov, and Verstra\"{e}te. A simple $k$-coloring of a multigraph $G$ is a decomposition of the edge multiset as a disjoint sum of $k$ simple graphs which are referred as \emph{colors}. A subgraph $H$ of a multigraph $G$ is called \emph{multicolored} if all of its edges have distinct colors. The multicolor extremal number, $\mathrm{ex}_k(n,H)$, is defined as the maximum number of edges in an $n$-vertex multigraph that has a simple $k$-coloring containing no multicolored copy of $H$.
Two natural constructions for this problem are as follows: When $k < e(H)$, it is clear that the unique extremal construction comes from $k$ copies of the complete graph. Even when $k \ge e(H)$, one can consider the multigraph consisting of $e(H)-1$ copies of the complete graph. A second natural construction is to take the sum of $k$ copies of a fixed extremal $H$-free graph. Keevash, Saks, Sudakov, and Verstra\"{e}te showed that the multicolor extremal problem always admits one of the two natural constructions when $H$ is a complete graph of any fixed order. Moreover, they conjectured the same for every color-critical graphs and proved it for 3-color-critical graphs.
We prove their conjecture for 4-color-critical graphs and for `most' $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\"{e}te.
