A Density Turán Theorem

0474851 - ÚI 2018 RIV US eng J - Journal Article
Narins, L. - Tran, Tuan
A Density Turán Theorem.
Journal of Graph Theory. Roč. 85, č. 2 (2017), s. 496-524. ISSN 0364-9024. E-ISSN 1097-0118
Institutional support: RVO:67985807
Keywords : Turán’s theorem * stability method * multipartite version
OECD category: Pure mathematics
Impact factor: 0.685, year: 2017

Let F be a graph that contains an edge whose deletion reduces its chromatic number. For such a graph F, a classical result of Simonovits from 1966 shows that every graph on n > n(0)(F) vertices with more than chi(F)-2/chi(F)-1. n(2)/2 edges contains a copy of F. In this article we derive a similar theorem for multipartite graphs. For a graph H and an integer l >= v(H), let d(l) (H) be the minimum real number such that every l-partite graph whose edge density between any two parts is greater than d(l)(H) contains a copy of H. Our main contribution in this article is to show that d(l) (H) = chi(H)-2/chi(H)-1 for all l >= l(0)(H) sufficiently large if and only if H admits a vertex-coloring with chi(H) - 1 colors such that all color classes but one are independent sets, and the exceptional class induces just a matching. When H is a complete graph, this recovers a result of Pfender (Combinatorica 32 (2012), 483-495). We also consider several extensions of Pfender's result.
Permanent Link: http://hdl.handle.net/11104/0271784