G-97-01
Nesticity
and BibTeX reference
A hypergraph H=(X,E) is nested if its edges are pairwise disjoint or included one into the other. The nesticity of H is defined as the smallest number of nested partial hypergraphs into which H can be partitioned. Determining the nesticity of H reduces to graph coloring. Hypergraphs of nesticity 2 are shown to be unimodular. A prehypergraph H' is obtained from a hypergraph H by specifying that some or all vertices from a given subset of each edge may be deleted. H' is thus a set of hypergraphs, called its realizations. Determining the nesticity of a prehypergraph H', i.e., the smallest nesticity of its realizations, reduces to satisfiability.
Published January 1997 , 14 pages
This cahier was revised in May 1997