Jaehyeon Seo (서재현), A rainbow Turán problem for color-critical graphs

For 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$?

Keevash, Saks, Sudakov, and Verstraëte 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 is a joint work with Debsoumya Chakraborti, Jaehoon Kim, Hyunwoo Lee, and Hong Liu.

IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.