✦ LIBER ✦

A lower bound on the independence number of arbitrary hypergraphs

✍ Scribed by Thiele, Torsten

Publisher: John Wiley and Sons
Year: 1999
Tongue: English
Weight: 104 KB
Volume: 30
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199903)30:3<213::aid-jgt6>3.0.co;2-q

No coin nor oath required. For personal study only.

✦ Synopsis

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(v)). This lower bound is sharp when H is a match, and it generalizes known bounds of Caro/Wei and Caro/Tuza for ordinary graphs and uniform hypergraphs. Furthermore, an algorithm for computing independent sets of size as guaranteed by the lower bound is given.

📜 SIMILAR VOLUMES

A lower bound for the crossing number of

A lower bound for the crossing number of Cm × Cn

✍ Gelasio Salazar 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 67 KB

A sharp edge bound on the interval numbe

A sharp edge bound on the interval number of a graph

✍ Balogh, J�zsef; Pluh�r, Andr�s 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 201 KB 👁 2 views

The interval number of a graph G, denoted by i(G), is the least natural number t such that G is the intersection graph of sets, each of which is the union of at most t intervals. Here we settle a conjecture of Griggs and West about bounding i(G) in terms of e, that is, the number of edges in G. Name