Lower bounds for the independence and \(k\)-independence number of graphs using the concept of degenerate degrees
From MaRDI portal
Publication:260061
DOI10.1016/j.dam.2015.09.023zbMath1332.05111arXiv1507.07194MaRDI QIDQ260061
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
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