Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas
type: Item
instance of: scholarly article
title: Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas
zbMATH Open document ID: 0611.05045
DOI: 10.1016/0097-3165(86)90060-9
author: Nathan Linial
author: Ron Aharoni
published in: Journal of Combinatorial Theory. Series A
publication date: 1986-01-01T00:00:00Z
review text: The authors prove (using transversal theory) infinite versions of the result due to P. D. Seymour (minimal non-two-colorable hypergraph on n vertices has at least n edges) and an unpublished result of M. Tarsi. They give a characterization of the structure of minimal unsatisfiable CNF formulas in n variables containing exactly \(n+1\) clauses and its geometrical interpretation.
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 3987323
zbMATH Keywords: minimal unsatisfiable formulae
zbMATH Keywords: minimal non-two-colorable hypergraph
zbMATH Keywords: König's duality theorem
zbMATH Keywords: transversal theory
reviewed by: Leszek S. Zaremba
MaRDI profile type: Publication
full work available at URL: 0097-3165(86)90060-9
OpenAlex ID: W2015211698
cites work: König's Duality Theorem for Infinite Bipartite Graphs
cites work: Deciding hypergraph 2-colourability by H-resolution
cites work: A generalization of Kónig's theorem
cites work: ON THE TWO-COLOURING OF HYPERGRAPHS
description: scientific article; zbMATH DE number 3987323