For given graphs over a common vertex set of size , what conditions on ensures a ‘colorful’ copy of , i.e. a copy of containing at most one edge from each ?
Keevash, Saks, Sudakov, and Verstraëte defined to be the maximum total number of edges of the graphs on a common vertex set of size having no colorful copy of . They completely determined for large by showing that, depending on the value of , 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 -color-critical graphs.
We prove their conjecture for -color-critical graphs and for almost all -color-critical graphs when . Moreover, we show that for every non-color-critical non-bipartite graphs, none of the two natural constructions is extremal for certain values of . This is a joint work with Debsoumya Chakraborti, Jaehoon Kim, Hyunwoo Lee, and Hong Liu.