A lower bound on independence in terms of degrees

DOI10.1016/J.DAM.2011.03.003zbMATH Open1218.05036OpenAlexW2020061266MaRDI QIDQ548268FDOQ548268

Jochen Harant

Publication date: 28 June 2011

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

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

zbMATH Keywords

independencestabilityconnected graph

Mathematics Subject Classification ID

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

Cites Work

• Clique is hard to approximate within \(n^{1-\epsilon}\)
• A lower bound on the independence number of a graph in terms of degrees
• On the independence number of a graph in terms of order and size
• Independence in connected graphs
• Foreword: Special issue on stability in graphs and related topics

Cited In (10)

• Lower bounds for the independence and \(k\)-independence number of graphs using the concept of degenerate degrees
• Transversals and independence in linear hypergraphs with maximum degree two
• Logical independence of the axioms characterizing the degree measure in van den Brink et al. (2008)
• Bounds on the independence number of a graph in terms of order, size and maximum degree
• On vertex independence number of uniform hypergraphs
• Lower bounds for constant degree independent sets
• The Fano plane and the strong independence ratio in hypergraphs of maximum degree 3
• An improved lower bound on the independence number of a graph
• Improved lower bounds on k‐independence
• New bounds on the independence number of connected graphs

This page was built for publication: A lower bound on independence in terms of degrees

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