Geodesic
Complexity of recognizing edge intersection graphsof hypergraphs with bounded above rank and multiplicity
Trudy Instituta matematiki, Tome 24 (2016) no. 2, pp. 98-105 
Yu. Metelsky; R. Shatsov. Complexity of recognizing edge intersection graphsof hypergraphs with bounded above rank and multiplicity. Trudy Instituta matematiki, Tome 24 (2016) no. 2, pp. 98-105. http://geodesic.mathdoc.fr/item/TIMB_2016_24_2_a9/
@article{TIMB_2016_24_2_a9,
     author = {Yu. Metelsky and R. Shatsov},
     title = {Complexity of recognizing edge intersection graphsof hypergraphs with bounded above rank and multiplicity},
     journal = {Trudy Instituta matematiki},
     pages = {98--105},
     year = {2016},
     volume = {24},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMB_2016_24_2_a9/}
}
TY  - JOUR
AU  - Yu. Metelsky
AU  - R. Shatsov
TI  - Complexity of recognizing edge intersection graphsof hypergraphs with bounded above rank and multiplicity
JO  - Trudy Instituta matematiki
PY  - 2016
SP  - 98
EP  - 105
VL  - 24
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/TIMB_2016_24_2_a9/
LA  - ru
ID  - TIMB_2016_24_2_a9
ER  - 
%0 Journal Article
%A Yu. Metelsky
%A R. Shatsov
%T Complexity of recognizing edge intersection graphsof hypergraphs with bounded above rank and multiplicity
%J Trudy Instituta matematiki
%D 2016
%P 98-105
%V 24
%N 2
%U http://geodesic.mathdoc.fr/item/TIMB_2016_24_2_a9/
%G ru
%F TIMB_2016_24_2_a9

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

Let $L^m_k$ denote the class of edge intersection graphs of hypergraphs with rank at most $k$ and multiplicity at most $m.$ It is proved that the problem of recognizing graphs of the class $L^m_k$ is NP-complete for fixed $k \ge 3,$ $m \ge 1.$

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

[2] Beineke L. W., “Derived graphs and digraphs”, Beitraege zur Graphentheorie, Teubner-Verlag, Leipzig, 1968, 17–33

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

[4] Naor J., Novick M. B., “An efficient reconstruction of a graph from its line graph in parallel”, J. Algorithms, 11 (1990), 132–143 | DOI | MR | Zbl

[5] 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

[6] Tashkinov V. A., “Kharakterizatsiya rebernykh grafov $p$-grafov”, Materialy 5-i Vsesoyuznoi konferentsii po problemam teoreticheskoi kibernetiki, Novosibirsk, 1980, 135–137

[7] Bermond J. C., Meyer J. C., “Graphs representatif des aretes d'un multigraphe”, J. Math. Pures Appl., 52 (1973), 299–308 | MR

[8] Hlineny P., Kratochvil J., “Computational complexity of the Krausz dimension of graphs”, Lecture Notes in Computer Science, 1335, 1997, 214–228 | DOI | MR | Zbl

[9] Glebova O., Metelsky Yu., Skums P., “Krausz dimension and its generalizations in special graph classes”, Discrete Mathematics and Theoretical Computer Science, 15:1 (2013), 107–120 | MR | Zbl

[10] Fellows M., Kratochvil J., Middendorf M., Pfeiffer F., “The complexity of induced minors and related problems”, Algorithmica, 13 (1995), 266–282 | DOI | MR | Zbl