Weighted variants of the Andrásfai-Erdős-Sós Theorem

Abstract

A well known result due to Andrásfai, Erdős, and Sós asserts that for $r\ge 2$ every $K_{r+1}$-free graph on $n$ vertices with $\delta (G)>\frac{3r-4}{3r-1}n$ is $r$-partite. We study related questions in the context of weighted graphs, which are motivated by recent work on the Ramsey-Turán problem for cliques.

arXiv comment8 figures; revised according to referee report

Cited by in corpus (1)

• A unified approach to hypergraph stability