Number of the records: 1
A Density Turán Theorem
- 1.
SYSNO ASEP 0474851 Document Type J - Journal Article R&D Document Type Journal Article Subsidiary J Článek ve WOS Title A Density Turán Theorem Author(s) Narins, L. (DE)
Tran, Tuan (UIVT-O)Source Title Journal of Graph Theory. - : Wiley - ISSN 0364-9024
Roč. 85, č. 2 (2017), s. 496-524Number of pages 29 s. Language eng - English Country US - United States Keywords Turán’s theorem ; stability method ; multipartite version Subject RIV BA - General Mathematics OECD category Pure mathematics Institutional support UIVT-O - RVO:67985807 UT WOS 000402151300014 EID SCOPUS 85018815115 DOI 10.1002/jgt.22075 Annotation 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. Workplace Institute of Computer Science Contact Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800 Year of Publishing 2018
Number of the records: 1