Geodesic
A note on independent sets in graphs with large minimum degree and small cliques
Jeremy Lyle1
1The University of Southern Mississippi
The electronic journal of combinatorics, Tome 21 (2014) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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-4))|V(G)|$ must be $(r-1)$-partite. An obvious consequence of this result is that the same degree threshold implies an independent set of order $(1/(r-1))|V(G)|$. The following paper provides improved bounds on the minimum degree which would imply the same conclusion. This problem was first considered by Brandt, and we provide improvements over these initial results for $r > 5$.
DOI : 10.37236/3881
Classification : 05C69, 05C07, 05C42, 05C35
Mots-clés : dense graphs, independent sets

Jeremy Lyle  1

1 The University of Southern Mississippi 
@article{10_37236_3881,
     author = {Jeremy Lyle},
     title = {A note on independent sets in graphs with large minimum degree and small cliques},
     journal = {The electronic journal of combinatorics},
     year = {2014},
     volume = {21},
     number = {2},
     doi = {10.37236/3881},
     zbl = {1300.05232},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/3881/}
}
TY  - JOUR
AU  - Jeremy Lyle
TI  - A note on independent sets in graphs with large minimum degree and small cliques
JO  - The electronic journal of combinatorics
PY  - 2014
VL  - 21
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/3881/
DO  - 10.37236/3881
ID  - 10_37236_3881
ER  - 
%0 Journal Article
%A Jeremy Lyle
%T A note on independent sets in graphs with large minimum degree and small cliques
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/3881/
%R 10.37236/3881
%F 10_37236_3881
Jeremy Lyle. A note on independent sets in graphs with large minimum degree and small cliques. The electronic journal of combinatorics, Tome 21 (2014) no. 2. doi: 10.37236/3881

Cité par Sources :