A Note On Independent Sets In Graphs With Large Minimum Degree and Small Cliques

Authors

Jeremy Lyle, University of Southern MississippiFollow

Document Type

Article

Publication Date

5-22-2014

Department

Mathematics

School

Mathematics and Natural Sciences

Abstract

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.

Publication Title

Electronic Journal of Combinatorics

Volume

21

Issue

2

Recommended Citation

Lyle, J. (2014). A Note On Independent Sets In Graphs With Large Minimum Degree and Small Cliques. Electronic Journal of Combinatorics, 21(2).
Available at: https://aquila.usm.edu/fac_pubs/19920