𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Improved lower bounds on k-independence

✍ Scribed by Yair Caro; Zsolt Tuza

Publisher
John Wiley and Sons
Year
1991
Tongue
English
Weight
418 KB
Volume
15
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A vertex set Y in a (hyper)graph is called k‐independent if in the sub(hyper)‐graph induced by Y every vertex is incident to less than k edges. We prove a lower bound for the maximum cardinality of a k‐independent setβ€”in terms of degree sequencesβ€”which strengthens and generalizes several previously known results, including TurΓ‘n's theorem.

πŸ“œ SIMILAR VOLUMES

Lower bounds on size and independence in
Lower bounds on size and independence inK4-free graphs
✍ Fraughnaugh, Kathryn L.; Locke, Stephen C. πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 131 KB πŸ‘ 1 views

We investigate lower bounds on the size of K 4 -free graphs. For several ranges of independence relative to order and for graphs with maximum degree 3 and 4, we find sharp lower bounds. We also evaluate Ramsey-type numbers over the classes of graphs with maximum degree 3 and with maximum degree 4.

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