On a rainbow extremal problem for color-critical graphs

Abstract

Given (Formula presented.) graphs (Formula presented.) over a common vertex set of size (Formula presented.), what is the maximum value of (Formula presented.) having no “colorful” copy of (Formula presented.), that is, a copy of (Formula presented.) containing at most one edge from each (Formula presented.) ? Keevash, Saks, Sudakov, and Verstraëte denoted this number as (Formula presented.) and completely determined (Formula presented.) for large (Formula presented.). In fact, they showed that, depending on the value of (Formula presented.), 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 (Formula presented.) that have only these two extremal constructions. We prove their conjecture for 4-color-critical graphs and for almost all (Formula presented.) -color-critical graphs when (Formula presented.). Moreover, we show that for every non-color-critical non-bipartite graphs, none of the two natural constructions is extremal for certain values of (Formula presented.). © 2023 Wiley Periodicals LLC.