Complexity of recognizing edge intersection graphsof hypergraphs with bounded above rank and multiplicity

Yu. Metelsky, R. Shatsov

Belarusian State University, Minsk

Abstract: Let $L^m_k$ denote the class of edge intersection graphs of hypergraphs with rank at most $k$ and multiplicity at most $m.$ It is proved that the problem of recognizing graphs of the class $L^m_k$ is NP-complete for fixed $k \ge 3,$ $m \ge 1.$

UDC: 519.1

Received: 26.09.2016