Abstract:
Dependencies of Helly and Krauz dimension are investigated ($r$-mino and line graphs of $k$-uniform hypergraphs, respectively). It is shown that intersection of $r$-mino and line graphs of $k$-uniform hypergraphs classes is not empty for any $r\ge k\ge 2$. It is proven that helly dimension can be computed in a polynomial time against krauz dimension and maximal vertex degree of graph. Boundaries of helly dimension in terms of krauz dimension are given. It is proven that "$kd_s(G)\le 3$" recognition problem is $NP$-complete in the $3$-mino class.