A new lower bound on the independence number of graphs

DOI10.1016/J.DAM.2012.10.001MaRDI QIDQ1946229zbMATH OpenOpenAlexFDO

Authors Eric Angel, Romain Campigotto, Christian Laforest

Publication date 18 April 2013

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

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

zbMATH Keywords

expectationindependence numbervariancevertex cover

Mathematics Subject Classification ID

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

Recommendations

• A lower bound on the independence number of a graph
• scientific article; zbMATH DE number 1112370
• scientific article; zbMATH DE number 1990716
• A lower bound on the independence number of a graph in terms of degrees
• A probabilistic lower bound on the independence number of graphs

Cited in

(28)

• A generalization of the Hoffman-Lovász upper bound on the independence number of a regular graph
• A probabilistic lower bound on the independence number of graphs
• Revisit the Lovász local lemma
• A lower bound on the independence number of a graph
• An upper bound on the independence number of a graph computable in polynomial-time
• Bounds and extremal graphs for degenerate subsets, dynamic monopolies, and partial incentives
• Lower bounds for the independence and \(k\)-independence number of graphs using the concept of degenerate degrees
• A solution to an open problem on lower against number in graphs
• New Bounds of Induced Acyclic Graphoidal Decomposition Number of a Graph
• scientific article; zbMATH DE number 3989382 (Why is no real title available?)
• Improved lower bounds on k‐independence
• On vertex independence number of uniform hypergraphs
• New lower bounds on independence number in triangle-free graphs in terms of order, maximum degree and girth
• Lower bounds on size and independence inK4-free graphs
• scientific article; zbMATH DE number 1112370 (Why is no real title available?)
• scientific article; zbMATH DE number 1990716 (Why is no real title available?)
• New bounds on the independence number of connected graphs
• An improved lower bound on the independence number of a graph
• Bounds on the independence number of a graph in terms of order, size and maximum degree
• A new notion of vertex independence and rank for finite graphs
• New analytical lower bounds on the clique number of a graph
• New results on \(k\)-independence of graphs
• Cut-edges and the independence number
• scientific article; zbMATH DE number 2192179 (Why is no real title available?)
• Lower bounds on the independence number of certain graphs of odd girth at least seven
• Machine learning predicts graph properties: clique, girth, and independent numbers
• New bounds on domination and independence in graphs
• Automated conjecturing. I: Fajtlowicz's Dalmatian heuristic revisited

This page was built for publication: A new lower bound on the independence number of graphs

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