A note on independent sets in graphs with large minimum degree and small cliques
type: Item
instance of: scholarly article
title: A note on independent sets in graphs with large minimum degree and small cliques
zbMATH Open document ID: 1300.05232
author: Jeremy Lyle
published in: The Electronic Journal of Combinatorics
publication date: 2014-09-04T00:00:00Z
full work available at URL: v21i2p38
review text: Summary: 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 \textit{B. Andrásfai} et al. [Discrete Math. 8, 205--218 (1974; Zbl 0284.05106)] 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\).
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C07
Mathematics Subject Classification ID: 05C42
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 6340205
zbMATH Keywords: dense graphs
zbMATH Keywords: independent sets
MaRDI profile type: Publication
cites work: On the connection between chromatic number, maximal clique and minimal degree of a graph
cites work: On a Ramsey-Turán type problem
cites work: Note on the structure of graphs with bounded clique number
cites work: Q5610920
cites work: On the structure of triangle-free graphs of large minimum degree
cites work: Q4401979
cites work: On the chromatic number of triangle-free graphs of large minimum degree
cites work: Q5781249
description: scientific article; zbMATH DE number 6340205