Хеллиева размерность реберных графов $k$-униформных гиперграфов

Исследуется взаимосвязь хеллиевой и краусовой размерностей (соответственно графов $r$-мино и реберных графов $k$-униформных гиперграфов). Показано, что пересечение классов $r$-мино и реберных графов $k$-униформных гиперграфов не пусто для любых $r\ge k\ge2$. Доказано, что хеллиева размерность может быть вычислена за полиномиальное время от максимальной степени вершин и краусовой размерности графа. Приведены оценки на хеллиеву размерность в терминах краусовой размерности и максимальной степени вершин в графе. Доказано, что задача распознавания "$kd_s(G)\le 3$" является $NP$-трудной в классе $3$-мино.