𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Random hypergraph coloring algorithms and the weak chromatic number

✍ Scribed by Jeanette Schmidt-Pruzan; Eli Shamir; Eli Upfal

Publisher
John Wiley and Sons
Year
1985
Tongue
English
Weight
610 KB
Volume
9
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 upper and lower bounds for the weak chromatic number of uniform hypergra p hs.

πŸ“œ 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

Post's closed systems and the weak chrom
Post's closed systems and the weak chromatic number of hypergraphs
✍ C. Benzaken πŸ“‚ Article πŸ“… 1978 πŸ› Elsevier Science 🌐 English βš– 689 KB

In the Post lattice of the families of closed systems (r.e. sets CT ooolean functions closed with respect to composition) the particular systems of mionotonic functions are closely related to the classitication of hypergraphs by their weak chromatic numbers. It is shown also that ffor k r 3, the k-c

Acyclic graph coloring and the complexit
Acyclic graph coloring and the complexity of the star chromatic number
✍ David R. Guichard πŸ“‚ Article πŸ“… 1993 πŸ› John Wiley and Sons 🌐 English βš– 294 KB

## Abstract Star chromatic number, introduced by A. Vince, is a natural generalization of chromatic number. We consider the question, β€œWhen is Ο‡\* < Ο‡?” We show that Ο‡\* < Ο‡ if and only if a particular digraph is acyclic and that the decisioin problem associated with this question is probably not i

Vizing's coloring algorithm and the fan
Vizing's coloring algorithm and the fan number
✍ Diego Scheide; Michael Stiebitz πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 199 KB

## Abstract Most upper bounds for the chromatic index of a graph come from algorithms that produce edge colorings. One such algorithm was invented by Vizing [Diskret Analiz 3 (1964), 25–30] in 1964. Vizing's algorithm colors the edges of a graph one at a time and never uses more than Ξ”+Β΅ colors, wh