Geodesic
Helly dimension of line graphs of $k$-uniform hypergraphs
Trudy Instituta matematiki, Tome 18 (2010) no. 2, pp. 55-59 
E. V. Krylov. Helly dimension of line graphs of $k$-uniform hypergraphs. Trudy Instituta matematiki, Tome 18 (2010) no. 2, pp. 55-59. http://geodesic.mathdoc.fr/item/TIMB_2010_18_2_a4/
@article{TIMB_2010_18_2_a4,
     author = {E. V. Krylov},
     title = {Helly dimension of line graphs of $k$-uniform hypergraphs},
     journal = {Trudy Instituta matematiki},
     pages = {55--59},
     year = {2010},
     volume = {18},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMB_2010_18_2_a4/}
}
TY  - JOUR
AU  - E. V. Krylov
TI  - Helly dimension of line graphs of $k$-uniform hypergraphs
JO  - Trudy Instituta matematiki
PY  - 2010
SP  - 55
EP  - 59
VL  - 18
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/TIMB_2010_18_2_a4/
LA  - ru
ID  - TIMB_2010_18_2_a4
ER  - 
%0 Journal Article
%A E. V. Krylov
%T Helly dimension of line graphs of $k$-uniform hypergraphs
%J Trudy Instituta matematiki
%D 2010
%P 55-59
%V 18
%N 2
%U http://geodesic.mathdoc.fr/item/TIMB_2010_18_2_a4/
%G ru
%F TIMB_2010_18_2_a4

Voir la notice de l'article provenant de la source Math-Net.Ru

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.

[1] Emelichev V.A., Melnikov O.I., Sarvanov V.I., Tyshkevich R.I., Lektsii po teorii grafov, Nauka, M., 1990 | MR | Zbl

[2] Metelsky Y., Tyshkevich R., “Line graphs of Helly hyperhgraphs”, SIAM Journal of Discrete Mathematics, 16:3 (2003), 438–448 | DOI | MR | Zbl

[3] Morgan D., “Useful names for vertices: An introduction to dynamic implicit informative labeling schemes”, TR05-04, University of Alberta, 2005

[4] Krylov E.V., Perez Chernov A.Kh., “Algoritm raspoznavaniya $r$-mino”, Vestn. BGU. Ser. 1, 2008, no. 1, 98–101

[5] Krylov E.V., “Zadacha nakhozhdeniya khellievoi razmernosti grafa”, Sb. rabot 65-i nauch. konf. studentov i aspirantov Belgosuniversiteta, v. 2, BGU, Minsk, 2008, 57–59

[6] Poljak S., Rodl V., Turzik D., “Complexity of representations of graphs by set systems”, Discrete Applied Mathematics, 1981, no. 3, 301–312 | DOI | MR | Zbl

[7] Levin A.G., Tyshkevich R.I., “Rebernye gipergrafovy”, Diskret. matematika, 5:1 (1993), 112–129 | MR | Zbl

[8] Metelskii Yu.M., Suzdal S.V., Tyshkevich R.I., “Raspoznavanie grafov peresechenii reber lineinykh 3-uniformnykh gipergrafov”, Trudy Instituta matematiki NAN Belarusi, 7 (2001), 76–92