Interpolating between bounds on the independence number

DOI10.1016/J.DISC.2010.05.026MaRDI QIDQ708394zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

independencetriangle-free graph

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(8)

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

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)