Probabilistic analysis of strong hypergraph coloring algorithms and the strong chromatic number
type: Item
instance of: scholarly article
title: Probabilistic analysis of strong hypergraph coloring algorithms and the strong chromatic number
zbMATH Open document ID: 0624.05049
DOI: 10.1016/0012-365X(87)90101-4
author: Jeanette P. Schmidt
published in: Discrete Mathematics
publication date: 1987-01-01T00:00:00Z
review text: The main results of this article are the representation of algorithms for several strong coloring problems (that are well-defined partitions of the set of vertices of a hypergraph in certain color sets) and the analysis of their performance in spaces of random hypergraphs. The so-called strong coloring algorithms \({\mathfrak KL}\gamma\) are fully described, they are proved in detail by using many theorems and lemmata and they exist of three phases which are analysed exactly. Furthermore it is shown that in these spaces the number of colors which are used by these algorithms is almost surely within a small constant factor (less than 4) of the strong chromatic number of the hypergraph. The article also contains a small summary of theorems concerning weak colorings and sparse hypergraphs and refers to some questions which are left open.
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 4012661
zbMATH Keywords: algorithms
zbMATH Keywords: coloring problems
zbMATH Keywords: random hypergraphs
zbMATH Keywords: strong coloring algorithms
zbMATH Keywords: strong chromatic number
zbMATH Keywords: weak colorings
zbMATH Keywords: sparse hypergraphs
reviewed by: Heinz-Joachim Presia
MaRDI profile type: Publication
cites work: Q5615282
cites work: Q5668915
cites work: Cliques in random graphs
cites work: Q4773670
cites work: Sur la cardinalite maximum des couplages d'hypergraphes aléatoires uniformes
cites work: Couplages et transversaux généralises d'un hypergraphe infini
cites work: A threshold for perfect matchings in random d-pure hypergraphs
cites work: Random hypergraph coloring algorithms and the weak chromatic number
cites work: Component structure in the evolution of random hypergraphs
cites work: Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces
cites work: Asymptotical Estimations for the Number of Cliques of Uniform Hypergraphs
full work available at URL: 0012-365x(87)90101-4
OpenAlex ID: W2054534871
description: scientific article; zbMATH DE number 4012661