𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the chromatic number and independence number of hypergraph products

✍ Scribed by Dhruv Mubayi; Vojtěch Rödl

Book ID
108167407
Publisher
Elsevier Science
Year
2007
Tongue
English
Weight
106 KB
Volume
97
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

The chromatic numbers of random hypergra
The chromatic numbers of random hypergraphs
✍ Michael Krivelevich; Benny Sudakov 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 261 KB 👁 1 views

For a pair of integers 1 F ␥r, the ␥-chromatic number of an r-uniform Ž . hypergraph H s V, E is the minimal k, for which there exists a partition of V into subsets < < T, . . . , T such that e l T F ␥ for every e g E. In this paper we determine the asymptotic 1 k i Ž . behavior of the ␥-chromatic n

Random hypergraph coloring algorithms an
Random hypergraph coloring algorithms and the weak chromatic number
✍ Jeanette Schmidt-Pruzan; Eli Shamir; Eli Upfal 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 610 KB

We present a hypergraph coloring algorithm and analyze its performance in spaces of random hypergraphs. In these spaces the number of colors used by our algorithm is almost surely within a small constant factor (less than 2) of the weak chromatic number of the hypergraph. This also establishes new u

Chromatic numbers of hypergraphs and cov
Chromatic numbers of hypergraphs and coverings of graphs
✍ Zevi Miller; Heinrich Müller 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 284 KB

Burr recently proved [3] that for positive integers m , , m 2 , . . , , m, and any graph G we have x(G) 5 &, if and only if G can be expressed as the edge disjoint union of subgraphs F, satisfying x(F,) 5 m,. This theorem is generalized to hypergraphs. By suitable interpretations the generalization