An improved lower bound on the independence number of a graph

DOI10.1016/J.DAM.2014.07.001zbMATH Open1303.05137OpenAlexW2081617938MaRDI QIDQ477342FDOQ477342

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

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

zbMATH Keywords

independencevertex-cover

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Lower bounds on the independence number in terms of the degrees
• A new lower bound on the independence number of graphs
• A new lower bound on the independence number of a graph and applications
• A lower bound on independence in terms of degrees
• On the independence number of a graph in terms of order and size
• Independent domination in graphs: A survey and recent results
• The potential of greed for independence
• New Lower Bounds for the Independence Number of Sparse Graphs and Hypergraphs
• On the independent domination number of regular graphs
• Title not available (Why is that?)
• On the theory of graphs
• Independence in connected graphs
• Independence, clique size and maximum degree
• Independence in graphs with maximum degree four
• Sharp bounds on the order, size, and stability number of graphs
• Independence, odd girth, and average degree
• The independence number in graphs of maximum degree three
• Lower bounds on the independence number of certain graphs of odd girth at least seven

Cited In (11)

• 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
• 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
• Title not available (Why is that?)
• On the \(\ell\)-connectivity of a graph
• Title not available (Why is that?)
• Improved lower bounds on k‐independence
• 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)