Hypergraphic Degree Sequences are Hard

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


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:



  • There are currently no refbacks.