An improved lower bound on the independence number of a graph

DOI10.1016/J.DAM.2014.07.001MaRDI QIDQ477342zbMATH OpenOpenAlexFDO

Authors Michael A. Henning, Christian Löwenstein

Publication date 3 December 2014

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

Full work available at URL https://doi.org/10.1016/j.dam.2014.07.001

zbMATH Keywords

independencevertex-cover

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Paths and cycles (05C38)

Recommendations

• scientific article; zbMATH DE number 1112370
• A probabilistic lower bound on the independence number of graphs
• New bounds on the independence number of connected graphs
• Bounds on the independence number of a graph in terms of order, size and maximum degree
• A lower bound on the independence number of a graph in terms of degrees and local clique sizes

Cites work

• scientific article; zbMATH DE number 3675940 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• A lower bound on independence in terms of degrees
• A new lower bound on the independence number of a graph and applications
• A new lower bound on the independence number of graphs
• Independence in connected graphs
• Independence in graphs with maximum degree four
• Independence, clique size and maximum degree
• Independence, odd girth, and average degree
• Independent domination in graphs: A survey and recent results
• Lower bounds on the independence number in terms of the degrees
• Lower bounds on the independence number of certain graphs of odd girth at least seven
• New lower bounds for the independence number of sparse graphs and hypergraphs
• On the independence number of a graph in terms of order and size
• On the independent domination number of regular graphs
• On the theory of graphs
• Sharp bounds on the order, size, and stability number of graphs
• The independence number in graphs of maximum degree three
• The potential of greed for independence

Cited in

(13)

• A note on eigenvalue bounds for independence numbers of non-regular graphs
• Bounds on the independence number of a graph in terms of order, size and maximum degree
• The lower bound on independence number.
• A lower bound on the independence number of a graph
• A generalization of the Hoffman-Lovász upper bound on the independence number of a regular graph
• Retracted: A remark on the weak Turán's theorem
• An upper bound on the independence number of a graph computable in polynomial-time
• Lower bounds on the independence number of certain graphs of odd girth at least seven
• scientific article; zbMATH DE number 3989382 (Why is no real title available?)
• On the -connectivity of a graph
• Improved lower bounds on k‐independence
• scientific article; zbMATH DE number 1503636 (Why is no real title available?)
• New bounds on the independence number of connected graphs

This page was built for publication: An improved lower bound on the independence number of a graph

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