On a rainbow extremal problem for color-critical graphs

Abstract

Given k graphs G(1), ... ,G(k) over a common vertex set of size n, what is the maximum value of Sigma(i is an element of[k])e(G(i)) having no "colorful" copy of H, that is, a copy of H containing at most one edge from each G(i)? Keevash, Saks, Sudakov, and Verstraete denoted this number as ex(k)(n,H) and completely determined ex(k)(n,K-r) for large n. In fact, they showed that, depending on the value of k, one of the two natural constructions is always the extremal construction. Moreover, they conjectured that the same holds for every color-critical graphs, and proved it for 3-color-critical graphs. They also asked to classify the graphs H that have only these two extremal constructions. We prove their conjecture for 4-color-critical graphs and for almost all 4-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.