Lower bounds for the independence and \(k\)-independence number of graphs using the concept of degenerate degrees

DOI10.1016/j.dam.2015.09.023zbMath1332.05111arXiv1507.07194MaRDI QIDQ260061

Manouchehr Zaker

Publication date: 18 March 2016

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

Full work available at URL: https://arxiv.org/abs/1507.07194

zbMATH Keywords

greedy algorithmindependent setdegeneracy\(k\)-independent set

Mathematics Subject Classification ID

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A lower bound on independence in terms of degrees
• Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
• Large induced degenerate subgraphs
• Lower bounds on the stability number of graphs computed in terms of degrees
• A probabilistic lower bound on the independence number of graphs
• Lower bounds on the independence number in terms of the degrees
• A note on greedy algorithms for the maximum weighted independent set problem
• A new lower bound on the independence number of graphs
• New approach to the \(k\)-independence number of a graph
• Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs
• Smallest-last ordering and clustering and graph coloring algorithms
• Improved lower bounds on k‐independence
• Balanced graphs and network flows
• Size and independence in triangle‐free graphs with maximum degree three
• A lower bound on the independence number of a graph in terms of degrees
• k-Degenerate Graphs
• On the independence number of a graph in terms of order and size