A lower bound on the independence number of a graph in terms of degrees

DOI10.7151/dmgt.1335zbMath1138.05051OpenAlexW2044686350MaRDI QIDQ5437226

Ingo Schiermeyer, Jochen Harant

Publication date: 18 January 2008

Published in: Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Full work available at URL: https://www.db-thueringen.de/servlets/MCRFileNodeServlet/dbt_derivate_00046448/2083-5892_26_2006_3_431-437.pdf

zbMATH Keywords

independencestabilitygreedy algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (5)

On vertex independence number of uniform hypergraphs ⋮ Independence in connected graphs ⋮ A lower bound on independence in terms of degrees ⋮ GreedyMAX-type Algorithms for the Maximum Independent Set Problem ⋮ Lower bounds for the independence and \(k\)-independence number of graphs using the concept of degenerate degrees

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