An extension of Turán's theorem, uniqueness and stability

zbMATH Open1298.05169arXiv1403.3801MaRDI QIDQ463041FDOQ463041

Authors: Peter Allen, Julia Böttcher, Jan Hladký, Diana Piguet 

Publication date: 23 October 2014

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: We determine the maximum number of edges of an $n$-vertex graph $G$ with the property that none of its $r$-cliques intersects a fixed set $MsubsetV(G)$. For $(r-1)|M|gen$, the $(r-1)$-partite Turan graph turns out to be the unique extremal graph. For $(r-1)|M|<n$, there is a whole family of extremal graphs, which we describe explicitly. In addition we provide corresponding stability results.

Full work available at URL: https://arxiv.org/abs/1403.3801

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Exact stability for Turán's theorem
• Extension of Turán's theorem to the 2-stability number
• scientific article; zbMATH DE number 16062
• scientific article
• An extension of a uniform asymptotic stability theorem by Matrosov
• A Generalization of the Turán Theorem and Its Applications
• An extension of a uniqueness theorem of J. A. Goldstein
• scientific article; zbMATH DE number 492678
• Some Stability and Exact Results in Generalized Turán Problems
• scientific article; zbMATH DE number 1489892

zbMATH Keywords

graph theoryTuran's theorem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The number of graphs without forbidden subgraphs
• Large generalized books are \(p\)-good
• A Density Corrádi–Hajnal Theorem
• Stability for large forbidden subgraphs
• Turánnical hypergraphs

Cited In (4)

• Extremal graphs for intersecting cliques
• Large joints in graphs
• A new Turán-type theorem for cliques in graphs
• Stability version of Dirac's theorem and its applications for generalized Turán problems

This page was built for publication: An extension of Turán's theorem, uniqueness and stability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q463041)