On the independence number of a graph in terms of order and size

DOI10.1016/S0012-365X(00)00298-3zbMath1030.05091OpenAlexW2134955799MaRDI QIDQ5937455

Jochen Harant, Ingo Schiermeyer

Publication date: 12 July 2001

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

Full work available at URL: https://doi.org/10.1016/s0012-365x(00)00298-3

Mathematics Subject Classification ID

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

Related Items (25)

A lower bound on the independence number of a graph in terms of degrees and local clique sizes ⋮ New bounds on the independence number of connected graphs ⋮ Bounds for the rank of a complex unit gain graph in terms of the independence number ⋮ Extremal values of the chromatic number for a given degree sequence ⋮ On vertex independence number of uniform hypergraphs ⋮ Independence in connected graphs ⋮ Skew-rank of an oriented graph and independence number of its underlying graph ⋮ Partitions of graphs into small and large sets ⋮ An improved lower bound on the independence number of a graph ⋮ Linear inequalities among graph invariants: Using GraPHedron to uncover optimal relationships ⋮ Independence, odd girth, and average degree ⋮ The robustness of resolvable block designs against the loss of whole blocks or replicates ⋮ Bounds on the independence number of a graph in terms of order, size and maximum degree ⋮ New potential functions for greedy independence and coloring ⋮ A lower bound on independence in terms of degrees ⋮ Minimum \(k\)-path vertex cover ⋮ Relation between the skew-rank of an oriented graph and the independence number of its underlying graph ⋮ Bounds on the nullity, the H-rank and the Hermitian energy of a mixed graph ⋮ GreedyMAX-type Algorithms for the Maximum Independent Set Problem ⋮ Adjacency rank and independence number of a signed graph ⋮ On zero-error codes produced by greedy algorithms ⋮ The \(k\)-path vertex cover in Cartesian product graphs and complete bipartite graphs ⋮ The \(k\)-path vertex cover of rooted product graphs ⋮ 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

This page was built for publication: On the independence number of a graph in terms of order and size