A lower bound on the independence number of a graph in terms of degrees and local clique sizes

DOI10.1016/j.dam.2015.06.009zbMath1339.05279OpenAlexW804772926MaRDI QIDQ298956

Ingo Schiermeyer, Dieter Rautenbach, Christoph Brause, Bert Randerath

Publication date: 21 June 2016

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

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

zbMATH Keywords

independent setchromatic numberclique

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Vertex degrees (05C07)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new lower bound on the independence number of a graph and applications
• Independence in connected graphs
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• New potential functions for greedy independence and coloring
• Normal hypergraphs and the perfect graph conjecture
• The potential of greed for independence
• On Representatives of Subsets
• On the independence number of a graph in terms of order and size