A lower bound on the independence number of a graph

DOI10.1016/S0012-365X(98)00048-XzbMath0958.05067OpenAlexW2023867568MaRDI QIDQ1584341

Jochen Harant

Publication date: 2 November 2000

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

Full work available at URL: https://doi.org/10.1016/s0012-365x(98)00048-x

zbMATH Keywords

stabilityindependence numberindependent vertex set

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

On vertex independence number of uniform hypergraphs, Two faces of greedy leaf removal procedure on graphs, On a polynomial fractional formulation for independence number of a graph, Constructing test functions for global optimization using continuous formulations of graph problems, A nonconvex quadratic optimization approach to the maximum edge weight clique problem, The \(k\)-regular induced subgraph problem, Statistical mechanics perspective on the phase transition in vertex covering of finite-connectivity random graphs, GreedyMAX-type Algorithms for the Maximum Independent Set Problem, New analytical lower bounds on the clique number of a graph

Uses Software

• GRAFFITI

Cites Work

• On conjectures of Graffiti
• Lower bounds on the stability number of graphs computed in terms of degrees
• The independence number of graphs in terms of degrees
• Independence and the Havel-Hakimi residue
• A probabilistic lower bound on the independence number of graphs
• A remark on the existence of finite graphs
• On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
• On the residue of a graph
• Degree sequences of graphs and dominance order
• On Dominating Sets and Independent Sets of Graphs
• Maxima for Graphs and a New Proof of a Theorem of Turán