Lower bounds on the stability number of graphs computed in terms of degrees

DOI10.1016/0012-365X(91)90357-8zbMath0755.05055WikidataQ127063911 ScholiaQ127063911MaRDI QIDQ1175993

O. J. Murphy

Publication date: 25 June 1992

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

zbMATH Keywords

stability numberlower boundsdegrees

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Related Items (14)

Largest domination number and smallest independence number of forests with given degree sequence ⋮ Partitions of graphs into small and large sets ⋮ Best monotone degree conditions for graph properties: a survey ⋮ Computing independent sets in graphs with large girth ⋮ RECOGNIZING BY ORDER AND DEGREE PATTERN OF SOME PROJECTIVE SPECIAL LINEAR GROUPS ⋮ On sequential heuristic methods for the maximum independent set problem ⋮ New potential functions for greedy independence and coloring ⋮ GreedyMAX-type Algorithms for the Maximum Independent Set Problem ⋮ A lower bound on the independence number of a graph ⋮ Extending the MAX algorithm for maximum independent set ⋮ New sufficient conditions for \(\alpha\)-redundant vertices ⋮ The independence number of graphs in terms of degrees ⋮ New analytical lower bounds on the clique number of a graph ⋮ Lower bounds for the independence and \(k\)-independence number of graphs using the concept of degenerate degrees

Cites Work

• Approximation algorithms for combinatorial problems
• Lower bounds on the independence number in terms of the degrees
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Lower bounds on the stability number of graphs computed in terms of degrees