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

DOI10.7151/DMGT.1335zbMATH Open1138.05051OpenAlexW2044686350MaRDI QIDQ5437226FDOQ5437226

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

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

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)

Cited In (18)

• 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
• Title not available (Why is that?)
• A lower bound on independence in terms of degrees
• The lower bound on independence number.
• GreedyMAX-type Algorithms for the Maximum Independent Set Problem
• 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
• Improving the Caro-Wei bound and applications to Turán stability
• 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
• Title not available (Why is that?)
• A degree sum condition concerning the connectivity and the independence number of a graph

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)