Interpolating between bounds on the independence number

DOI10.1016/J.DISC.2010.05.026zbMATH Open1213.05042OpenAlexW2001698828MaRDI QIDQ708394FDOQ708394

Authors: Anett Boßecker, Dieter Rautenbach 

Publication date: 11 October 2010

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://www.db-thueringen.de/servlets/MCRFileNodeServlet/dbt_derivate_00018227/IfM_Preprint_M09_26.pdf

Recommendations

• Independence in graphs a medley of popular tunes
• A lower bound on the independence number of a graph in terms of degrees and local clique sizes
• New lower bounds on independence number in triangle-free graphs in terms of order, maximum degree and girth
• A probabilistic lower bound on the independence number of graphs
• A lower bound on the independence number of arbitrary hypergraphs

zbMATH Keywords

independencetriangle-free graph

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Vertex degrees (05C07)

Cites Work

• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Paths in graphs
• A note on the independence number of triangle-free graphs
• A note on Ramsey numbers
• A note on the independence number of triangle-free graphs. II
• On the independence number of sparse graphs
• Large independent sets in regular graphs of large girth
• A dense infinite Sidon sequence
• On Turan's theorem for sparse graphs
• Locally dense independent sets in regular graphs of~large~girth -- an example of a new approach
• Title not available (Why is that?)
• Independent sets in graphs with triangles
• An upper bound on the Ramsey numbers R(3,k)

Cited In (8)

• A lower bound on the independence number of a graph in terms of degrees and local clique sizes
• The lower bound on independence number.
• A probabilistic lower bound on the independence number of graphs
• Title not available (Why is that?)
• Improving the Caro-Wei bound and applications to Turán stability
• On Selkow's bound on the independence number of graphs
• Independence in graphs a medley of popular tunes
• New analytical lower bounds on the clique number of a graph

This page was built for publication: Interpolating between bounds on the independence number

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