𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Chromatic Index of Hypergraphs and Shannon’s Theorem

✍ Scribed by Tomáš Dvořák

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
85 KB
Volume
21
Category
Article
ISSN
0195-6698

No coin nor oath required. For personal study only.

✦ Synopsis

A classical theorem of Claude Shannon states that for any multigraph G without loops, χ (G) ≤ 3 2 (G) . We suggest a generalization of Shannon's theorem to hypergraphs and prove it in case of hypergraphs without repeated edges of size 2.

📜 SIMILAR VOLUMES

On the Degree, Size, and Chromatic Index
On the Degree, Size, and Chromatic Index of a Uniform Hypergraph
✍ Noga Alon; Jeong Han Kim 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 274 KB

Let H be a k-uniform hypergraph in which no two edges share more than t common vertices, and let D denote the maximum degree of a vertex of H. We conjecture that for every =>0, if D is sufficiently large as a function of t, k, and =, then the chromatic index of H is at most (t&1+1Ât+=) D. We prove t

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

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

Interchange Theorems for Hypergraphs and
Interchange Theorems for Hypergraphs and Factorization of Their Degree Sequences
✍ A.A. Chernyak 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 124 KB

The aim of this paper is to unify interchange theorems and extend them to hypergraphs. To this end sufficient conditions for equality of the l 1 -distance between equivalence classes and the l 1 -distance between corresponding order-type functions are provided. The generality of this result is demon

Strong chromatic index of subset graphs
Strong chromatic index of subset graphs
✍ Quinn, Jennifer J.; Benjamin, Arthur T. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB 👁 2 views

The strong chromatic index of a graph G, denoted sq(G), is the minimum number of parts needed to partition the edges of G into induced matchings. For 0 ≤ k ≤ l ≤ m, the subset graph S m (k, l) is a bipartite graph whose vertices are the kand l-subsets of an m element ground set where two vertices ar

Subdivisions and the chromatic index of
Subdivisions and the chromatic index of r-graphs
✍ K. Kilakos; F. B. Shepherd 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 625 KB

Let T2 be the graph obtained from the Petersen graph by first deleting a vertex and then contracting an edge incident to a vertex of degree two. We give a simple characterization of the graphs that contain no subdivision of T2. This characterization is used to show that if every planar r-graph is r-