Threshold hypergraphs
type: Item
instance of: scholarly article
title: Threshold hypergraphs
zbMATH Open document ID: 0564.05043
DOI: 10.1016/0012-365X(85)90080-9
author: Jan Reiterman
author: Vojtěch Rödl
author: Edita Šiňajová
author: Miroslav Tuma
published in: Discrete Mathematics
publication date: 1985-01-01T00:00:00Z
review text: Threshold graphs were introduced by \textit{V. Chvátal} and \textit{P. L. Hammer} [Ann. Discrete Math. 1, 145-162 (1977; Zbl 0384.90091)]. They gave three equivalent characterizations of these graphs. These characterizations were generalized for hypergraphs by \textit{M. Ch. Golumbic} [Combinatorics, Keszthely 1976, Colloq. Math. János Bolyai 18, 419-428 (1978; Zbl 0398.05058)]. He asked whether these were equivalent or not. The answer is negative. The authors prove this by some constructions, and give three equivalent characterizations of the most general definition from the above three generalizations. On the end of this clear style paper we can find a result on the complexity of this property.
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 90C10
zbMATH DE Number: 3898935
zbMATH Keywords: threshold hypergraphs
zbMATH Keywords: integer programming
zbMATH Keywords: parallel processing
zbMATH Keywords: Threshold graphs
reviewed by: Péter L. Erdős
MaRDI profile type: Publication
cites work: Q4165164
cites work: Q4182796
cites work: Q3328583
cites work: A Graph-Theoretic Characterization of the $\text{PV}_{\text{chunk}}$ Class of Synchronizing Primitives
cites work: Q3050157
cites work: On an extension of Dijkstra's semaphore primitives
full work available at URL: 0012-365x(85)90080-9
OpenAlex ID: W4213070679
Recommended article: Threshold graphs
Recommended article: Threshold graphs and related topics
Recommended article: Threshold Dimension of Graphs
Recommended article: Quasi-threshold graphs
Recommended article: Hypergraphs with zero chromatic threshold
Recommended article: On the Chromatic Thresholds of Hypergraphs
Recommended article: Q5699789
Recommended article: Hamiltonian threshold graphs
Recommended article: The threshold dimension of a graph
Recommended article: Thresholds for classes of intersection graphs
description: scientific article; zbMATH DE number 3898935