A note on independent sets in graphs with large minimum degree and small cliques

MaRDI QIDQ405242zbMATH OpenFDO

Authors Jeremy Lyle

Publication date 4 September 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p38

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

dense graphsindependent sets

Mathematics Subject Classification ID

Vertex degrees (05C07) Extremal problems in graph theory (05C35) Density (toughness, etc.) (05C42) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

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\).

Recommendations

• Dense graphs with small clique number
• \(K_r\)-factors in graphs with low independence number
• Independence and graph homomorphisms graph homomorphisms
• Note on the structure of graphs with bounded clique number
• On independent sets in graphs with given minimum degree

Cites work

• scientific article; zbMATH DE number 3435529 (Why is no real title available?)
• scientific article; zbMATH DE number 3333194 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• Note on the structure of graphs with bounded clique number
• On a Ramsey-Turán type problem
• On the chromatic number of triangle-free graphs of large minimum degree
• On the connection between chromatic number, maximal clique and minimal degree of a graph
• On the structure of triangle-free graphs of large minimum degree

Cited in

(10)

• \(K_r\)-factors in graphs with low independence number
• Independent domination in bipartite cubic graphs
• Independent domination in subcubic graphs
• An improved upper bound on the independent domination number in cubic graphs of girth at least six
• On independent domination in planar cubic graphs
• Independent domination in subcubic graphs of girth at least six
• scientific article; zbMATH DE number 15666 (Why is no real title available?)
• Minimum Number ofk-Cliques in Graphs with Bounded Independence Number
• Sparse halves in K4‐free graphs
• Independent sets in K₆-free graphs with large degree

This page was built for publication: A note on independent sets in graphs with large minimum degree and small cliques

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q405242)