Hypergraphic Degree Sequences are Hard
In their celebrated 1960 paper Erd˝os and Gallai give an eective characterization of degree sequences of graphs. The analog problem for 3-hypergraphs has been open ever since. We solve it by showing that deciding degree sequences of 3-hypergraphs is NP-complete.
- There are currently no refbacks.