A lower bound on the independence number of a graph

DOI10.1016/S0012-365X(98)00048-XMaRDI QIDQ1584341zbMATH OpenOpenAlexFDO

Authors 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

independence numberindependent vertex setstability

Mathematics Subject Classification ID

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

Recommendations

• A lower bound on the independence number of a graph in terms of degrees
• scientific article; zbMATH DE number 1112370
• A new lower bound on the independence number of graphs
• An improved lower bound on the independence number of a graph
• A new lower bound on the independence number of a graph and applications
• A probabilistic lower bound on the independence number of graphs
• A lower bound on the independence number of arbitrary hypergraphs
• scientific article; zbMATH DE number 866059
• The upper and lower independence number of graphs
• A lower bound on the independence number of a graph in terms of degrees and local clique sizes

Cites work

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

Cited in

(27)

• A generalization of the Hoffman-Lovász upper bound on the independence number of a regular graph
• Lower bounds for constant degree independent sets
• A nonconvex quadratic optimization approach to the maximum edge weight clique problem
• The k-regular induced subgraph problem
• An upper bound on the independence number of a graph computable in polynomial-time
• A new lower bound on the independence number of graphs
• On a polynomial fractional formulation for independence number of a graph
• Lower bounds for the independence and \(k\)-independence number of graphs using the concept of degenerate degrees
• A solution to an open problem on lower against number in graphs
• GreedyMAX-type algorithms for the maximum independent set problem
• scientific article; zbMATH DE number 7403962 (Why is no real title available?)
• scientific article; zbMATH DE number 5778835 (Why is no real title available?)
• scientific article; zbMATH DE number 3989382 (Why is no real title available?)
• On vertex independence number of uniform hypergraphs
• Rank and chromatic number of a graph
• Lower bounds on size and independence inK4-free graphs
• scientific article; zbMATH DE number 1112370 (Why is no real title available?)
• scientific article; zbMATH DE number 1929307 (Why is no real title available?)
• scientific article; zbMATH DE number 3995720 (Why is no real title available?)
• Two faces of greedy leaf removal procedure on graphs
• New analytical lower bounds on the clique number of a graph
• A lower bound on the independence number of a graph in terms of degrees
• On average lower independence and domination numbers in graphs
• Constructing test functions for global optimization using continuous formulations of graph problems
• On the independence number of a graph in terms of order and size
• Statistical mechanics perspective on the phase transition in vertex covering of finite-connectivity random graphs
• Lower bounds on the independence number of certain graphs of odd girth at least seven

Describes a project that uses

Uses Software

• GRAFFITI

This page was built for publication: A lower bound on the independence number of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1584341)