𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A new lower bound on the independence number of graphs

✍ Scribed by Angel, Eric; Campigotto, Romain; Laforest, Christian

Book ID
122079920
Publisher
Elsevier Science
Year
2013
Tongue
English
Weight
228 KB
Volume
161
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

A Probabilistic lower bound on the indep
A Probabilistic lower bound on the independence number of graphs
✍ Stanley M. Selkow πŸ“‚ Article πŸ“… 1994 πŸ› Elsevier Science 🌐 English βš– 124 KB

Caro (1979) and Wei (1981) established a bound on the size of an independent set of a graph as a function of its degrees. In case the degrees of each vertex's neighbors are also known, we establish a lower bound which is tighter for most graphs.

A lower bound on the independence number
A lower bound on the independence number of a graph
✍ Jochen Harant πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 210 KB

A new lower bound on the independence number of a graph is established and an accompanying efficient algorithm constructing an independent vertex set the cardinality of which is at least this lower bound is given. (~

The lower bound on independence number
The lower bound on independence number
✍ Yusheng Li; Cecil C. Rousseau; Wen’an Zang πŸ“‚ Article πŸ“… 2002 πŸ› SP Science China Press 🌐 English βš– 323 KB
A lower bound on the independence number
A lower bound on the independence number of arbitrary hypergraphs
✍ Thiele, Torsten πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 104 KB πŸ‘ 3 views

We present a lower bound on the independence number of arbitrary hypergraphs in terms of the degree vectors. The degree vector of a vertex v is given by d is the number of edges of size m containing v. We define a function f with the property that any hypergraph H = (V, E) satisfies Ξ±(H) β‰₯ v∈V f (d