Počet záznamů: 1
A Density Turán Theorem
- 1.
SYSNO ASEP 0474851 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název A Density Turán Theorem Tvůrce(i) Narins, L. (DE)
Tran, Tuan (UIVT-O)Zdroj.dok. Journal of Graph Theory. - : Wiley - ISSN 0364-9024
Roč. 85, č. 2 (2017), s. 496-524Poč.str. 29 s. Jazyk dok. eng - angličtina Země vyd. US - Spojené státy americké Klíč. slova Turán’s theorem ; stability method ; multipartite version Vědní obor RIV BA - Obecná matematika Obor OECD Pure mathematics Institucionální podpora UIVT-O - RVO:67985807 UT WOS 000402151300014 EID SCOPUS 85018815115 DOI 10.1002/jgt.22075 Anotace 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. Pracoviště Ústav informatiky Kontakt Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800 Rok sběru 2018
Počet záznamů: 1