Geodesic
On the recognition algorithm of edge intersection graphs of linear $3$-uniform hypergraphs: prelarge cliques
Trudy Instituta matematiki, Tome 15 (2007) no. 2, pp. 78-89 
A. J. Perez Tchernov; R. I. Tyshkevich. On the recognition algorithm of edge intersection graphs of linear $3$-uniform hypergraphs: prelarge cliques. Trudy Instituta matematiki, Tome 15 (2007) no. 2, pp. 78-89. http://geodesic.mathdoc.fr/item/TIMB_2007_15_2_a8/
@article{TIMB_2007_15_2_a8,
     author = {A. J. Perez Tchernov and R. I. Tyshkevich},
     title = {On the recognition algorithm of edge intersection graphs of linear $3$-uniform hypergraphs: prelarge cliques},
     journal = {Trudy Instituta matematiki},
     pages = {78--89},
     year = {2007},
     volume = {15},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMB_2007_15_2_a8/}
}
TY  - JOUR
AU  - A. J. Perez Tchernov
AU  - R. I. Tyshkevich
TI  - On the recognition algorithm of edge intersection graphs of linear $3$-uniform hypergraphs: prelarge cliques
JO  - Trudy Instituta matematiki
PY  - 2007
SP  - 78
EP  - 89
VL  - 15
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/TIMB_2007_15_2_a8/
LA  - ru
ID  - TIMB_2007_15_2_a8
ER  - 
%0 Journal Article
%A A. J. Perez Tchernov
%A R. I. Tyshkevich
%T On the recognition algorithm of edge intersection graphs of linear $3$-uniform hypergraphs: prelarge cliques
%J Trudy Instituta matematiki
%D 2007
%P 78-89
%V 15
%N 2
%U http://geodesic.mathdoc.fr/item/TIMB_2007_15_2_a8/
%G ru
%F TIMB_2007_15_2_a8

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

Let $L^l_k$ be the class of edge intersection graphs of linear $k$-uniform hypergraphs. It is known that the recognition problem "$G\in L^l_k$" is $NP$-complete for $k\ge 3$, but there exists an algorithm deciding whether $G\in L^l_3$ for graphs $G$ with minimal vertex degree $\delta(G)\ge 10$. In this paper we provide the practical oriented modification of this algorithm.

[1] Degiorgi D.G., Simon K., “A dynamic algorithm for line graph recognition”, Lecture Notes in Computer Science, 1017, 1995, 37–48 | MR

[2] Lehot P.G.H., “An optimal algorithm to detect a line graph and output its root graph”, J. Assoc. Comput. Math., 21 (1974), 569–575 | MR | Zbl

[3] Roussopoulos N.D., “A max $\{m,n\}$ algorithm for determining the graph $H$ from its line graph G”, Inform. Process. Lett., 2 (1973), 108–112 | DOI | MR | Zbl

[4] Hliněný P., Kratochvíl J., “Computational complexity of the Krausz dimension of graphs”, Lecture Notes in Computer Science, 1335, 1997, 214–228 | MR | Zbl

[5] Naik R.N., Rao S.B., Shrikhande S.S., Singhi N.M., “Intersection graphs of k-uniform linear hypergraphs”, Europ. J. Combin., 3 (1982), 159–172 | MR | Zbl

[6] Jacobson M.S., Kezdy A.E., Lehel J., “Recognizing intersection graphs of linear uniform hypergraphs”, Graphs and Combinatorics, 3 (1997), 359–367 | MR

[7] Metelsky Yu., Tyshkevich R., “On line graphs of linear 3-uniform hypergraphs”, J. Graph Theory, 25 (1997), 243–251 | 3.0.CO;2-K class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[8] Prisner E., The role of clique multigraphs in intersection graph theory, manuscript, 1998 | Zbl

[9] Scums P.V., Suzdal S.V., Tyshkevich R.I., “Edge intersection graphs of linear 3-uniform hypergraphs”, Electronic Notes of Discrete Math., 22 (2005), 33–40 | DOI

[10] Skums P.V., Suzdal S.V., Tyshkevich R.I., “O poroge polinomialnoi razreshimosti dlya zadachi raspoznavaniya grafov peresechenii reber lineinykh $3$-uniformnykh gipergrafov”, Dokl. NAN Belarusi, 48:4 (2004), 29–34 | MR

[11] Berge C., Graphs and Hypergraphs, North-Holland, 1973 | MR | Zbl

[12] Levin A., Tyshkevich R., “Line hypergraphs”, Discrete Math. Appl., 3 (1993), 407–427 | MR | Zbl

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

[14] Perez Chernov A.Kh., Suzdal S.V., “Ob algoritme raspoznavaniya grafov peresechenii reber lineinykh 3-uniformnykh gipergrafov”, Trudy Instituta matematiki, 13:2 (2005), 55–59