A Density Turán Theorem

0474851 - ÚI 2018 RIV US eng J - Článek v odborném periodiku
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
Institucionální podpora: RVO:67985807
Klíčová slova: Turán’s theorem * stability method * multipartite version
Obor OECD: Pure mathematics
Impakt faktor: 0.685, rok: 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.
Trvalý link: http://hdl.handle.net/11104/0271784