Journal of Combinatorics

Volume 11 (2020)

Number 2

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

Pages: 305 – 328



Clara Marie Lüders (Fachbereich Mathematik, Universität Hamburg, Germany)

Christian Reiher (Fachbereich Mathematik, Universität Hamburg, Germany)


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.

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

Received 27 October 2017

Published 14 January 2020