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

DOI10.7151/DMGT.1335MaRDI QIDQ5437226zbMATH OpenOpenAlexFDO

Authors Jochen Harant, Ingo Schiermeyer

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)

Recommendations

• scientific article; zbMATH DE number 1112370
• The potential of greed for independence
• A probabilistic lower bound on the independence number of graphs
• A lower bound on the independence number of a graph in terms of degrees and local clique sizes
• A lower bound on the independence number of a graph

Cited in

(22)

• New lower bounds on independence number in triangle-free graphs in terms of order, maximum degree and girth
• Lower bounds for the independence and \(k\)-independence number of graphs using the concept of degenerate degrees
• The potential of greed for independence
• A lower bound on independence in terms of degrees
• scientific article; zbMATH DE number 5778835 (Why is no real title available?)
• The lower bound on independence number.
• On vertex independence number of uniform hypergraphs
• Lower bounds on the stability number of graphs computed in terms of degrees
• Lower bounds for constant degree independent sets
• A probabilistic lower bound on the independence number of graphs
• A lower bound on the independence number of a graph
• Independence in connected graphs
• Lower bounds on size and independence inK4-free graphs
• A new lower bound on the independence number of graphs
• Improving the Caro-Wei bound and applications to Turán stability
• On Selkow's bound on the independence number of graphs
• Fractional coloring with local demands and applications to degree-sequence bounds on the independence number
• 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?)
• New potential functions for greedy independence and coloring
• A degree sum condition concerning the connectivity and the independence number of a graph
• GreedyMAX-type algorithms for the maximum independent set problem

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

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