We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
On a rainbow extremal problem for color‐critical graphs.
- Authors
Chakraborti, Debsoumya; Kim, Jaehoon; Lee, Hyunwoo; Liu, Hong; Seo, Jaehyeon
- Abstract
Given k$$ k $$ graphs G1,...,Gk$$ {G}_1,\dots, {G}_k $$ over a common vertex set of size n$$ n $$, what is the maximum value of ∑i∈[k]e(Gi)$$ {\sum}_{i\in \left[k\right]}e\left({G}_i\right) $$ having no "colorful" copy of H$$ H $$, that is, a copy of H$$ H $$ containing at most one edge from each Gi$$ {G}_i $$? Keevash, Saks, Sudakov, and Verstraëte denoted this number as exk(n,H)$$ {\mathrm{ex}}_k\left(n,H\right) $$ and completely determined exk(n,Kr)$$ {\mathrm{ex}}_k\left(n,{K}_r\right) $$ for large n$$ n $$. In fact, they showed that, depending on the value of k$$ 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$$ H $$ that have only these two extremal constructions. We prove their conjecture for 4‐color‐critical graphs and for almost all r$$ r $$‐color‐critical graphs when r>4$$ 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$$ k $$.
- Subjects
RAINBOWS; LOGICAL prediction; BIPARTITE graphs; EXTREMAL problems (Mathematics)
- Publication
Random Structures & Algorithms, 2024, Vol 64, Issue 2, p460
- ISSN
1042-9832
- Publication type
Article
- DOI
10.1002/rsa.21189