Quickly proving the Andrásfai-Erdős-Sós-Theorem

2012/12/11 by Christian Reiher, Reiher, Christian
Mathematics · #Graph theory and applications #math.CO #msc:05C35 #msc:05D99

paper · pdf · doi:10.48550/arxiv.1212.2521

Withdrawn, since it turned out that the same proof was discovered earlier by Stephan Brandt, Combinatorica 23 (2003), no. 4, 693-696

arxiv created 2016/03/20 · arxiv updated 2016/03/22

Abstract

Given an integer r\gs 2, an important theorem first proved by B. Andrásfai, P. Erdős, and V. T. Sós 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.

Related

• Andrásfai--Erdős--Sós theorem under max-degree constraints
• A criterion for Andrásfai--Erdős--Sós type theorems and applications
• Andrásfai--Erdős--Sós theorem for the generalized triangle
• Extremal triangle-free and odd-cycle-free colourings of uncountable\n graphs
• A local approach to the Erdős-Sós conjecture