Počet záznamů: 1  

A Density Turán Theorem

  1. 1. 0474851 - UIVT-O 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
    Institucionální podpora: RVO:67985807
    Klíčová slova: Turán’s theorem * stability method * multipartite version
    Kód oboru RIV: BA - Obecná matematika
    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