Weighted variants of the Andrásfai–Erdős–Sós theorem

A well known result due to Andrásfai, Erdős, and Sós asserts that for $r \geqslant 2$ every $K_{r+1}$-free graph $G$ on $n$ vertices with $\delta (G) \gt \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.

Full Text (PDF format)

The second-named author was supported by the European Research Council (ERC grant PEPCo 724903).

Received 27 October 2017

Published 14 January 2020