On a rainbow extremal problem for color-critical graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917572375478272 |
|---|---|
| author | Chakraborti, Debsoumya Kim, Jaehoon Lee, Hyunwoo Liu, Hong Seo, Jaehyeon |
| author_facet | Chakraborti, Debsoumya Kim, Jaehoon Lee, Hyunwoo Liu, Hong Seo, Jaehyeon |
| contents | There has been extensive studies on the following question: given $k$ graphs $G_1,\dots, G_k$ over a common vertex set of size $n$, what conditions on $G_i$ ensures a `colorful' copy of $H$, i.e., a copy of $H$ containing at most one edge from each $G_i$? A lower bound on $\sum_{i\in [k]} e(G_i)$ enforcing a colorful copy of a given graph $H$ was considered by Keevash, Saks, Sudakov, and Verstraëte. They defined $\operatorname{ex}_k(n,H)$ to be the maximum total number of edges of the graphs $G_1,\dots, G_k$ on a common vertex set of size $n$ having no colorful copy of $H$. They completely determined $\operatorname{ex}_k(n,K_r)$ for large $n$ by showing that, depending on the value of $k$, 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 3-color-critical graphs.
We prove their conjecture for 4-color-critical graphs and for almost all $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ëte. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2204_02575 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | On a rainbow extremal problem for color-critical graphs Chakraborti, Debsoumya Kim, Jaehoon Lee, Hyunwoo Liu, Hong Seo, Jaehyeon Combinatorics 05C35, 05D99 There has been extensive studies on the following question: given $k$ graphs $G_1,\dots, G_k$ over a common vertex set of size $n$, what conditions on $G_i$ ensures a `colorful' copy of $H$, i.e., a copy of $H$ containing at most one edge from each $G_i$? A lower bound on $\sum_{i\in [k]} e(G_i)$ enforcing a colorful copy of a given graph $H$ was considered by Keevash, Saks, Sudakov, and Verstraëte. They defined $\operatorname{ex}_k(n,H)$ to be the maximum total number of edges of the graphs $G_1,\dots, G_k$ on a common vertex set of size $n$ having no colorful copy of $H$. They completely determined $\operatorname{ex}_k(n,K_r)$ for large $n$ by showing that, depending on the value of $k$, 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 3-color-critical graphs. We prove their conjecture for 4-color-critical graphs and for almost all $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ëte. |
| title | On a rainbow extremal problem for color-critical graphs |
| topic | Combinatorics 05C35, 05D99 |
| url | https://arxiv.org/abs/2204.02575 |