Quickly proving the Andr\'asfai-Erd\H{o}s-S\'os-Theorem

arXiv1212.2521MaRDI QIDQ6237932FDOQ6237932

Authors: Christian Reiher 

Publication date: 11 December 2012

Abstract: Given an integer $rgs2$, an important theorem first proved by B. Andr'asfai, P. ErdH{o}s, and V. T. S'os states that any $K_{r+1}$--free graph on $n$ vertices whose minimum degree is greater than $(3r-4)n/(3r-1)$ is $r$--colourable, and determines the graphs that are extremal in this context. The purpose of this note is to give an alternative proof of this result using a different idea.

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Extremal combinatorics (05D99)

This page was built for publication: Quickly proving the Andr\'asfai-Erd\H{o}s-S\'os-Theorem

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