Hypergraphic Degree Sequences are Hard

Antoine Deza, Asaf Levin, Syed Mohammad Meesum, Shmuel Onn

Abstract


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.

Full Text:

PDF

Refbacks

  • There are currently no refbacks.