RUS  ENG
Full version
JOURNALS // Proceedings of the Institute of Mathematics of the NAS of Belarus // Archive

Tr. Inst. Mat., 2010 Volume 18, Number 2, Pages 55–59 (Mi timb17)

Helly dimension of line graphs of $k$-uniform hypergraphs

E. V. Krylov

Belarusian State University

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.

UDC: 519.1

Received: 30.12.2009



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025