A Note on Independent Sets in Graphs with Large Minimum Degree and Small Cliques

Electronic Journal Of Combinatorics

Jeremy Lyle¹ 

关键词: Dense graphs;    Independent sets;   

DOI  :  

学科分类：离散数学和组合数学

来源: Electronic Journal Of Combinatorics

【 摘 要 】

Graphs with large minimum degree containing no copy of a clique on $r$ vertices ($K_r$) must contain relatively large independent sets. A classical result of Andrásfai, Erdős, and Sós implies that $K_r$-free graphs $G$ with degree larger than $((3r-7)/(3r

【 授权许可】

Others