Geodesic
A Finite Characterization and Recognition of Intersection Graphs of Hypergraphs with Rank at Most 3 and Multiplicity at Most 2 in the Class of Threshold Graphs
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 1, pp. 13-28.

Voir la notice de l'article provenant de la source Library of Science

We characterize the class L_3^2 of intersection graphs of hypergraphs with rank at most 3 and multiplicity at most 2 by means of a finite list of forbidden induced subgraphs in the class of threshold graphs. We also give an O(n)-time algorithm for the recognition of graphs from L_3^2 in the class of threshold graphs, where n is the number of vertices of a tested graph.
Keywords: intersection graph, hypergraph rank, hypergraph multiplicity, forbidden induced subgraph, threshold graph 
@article{DMGT_2017_37_1_a1,
     author = {Metelsky, Yury and Schemeleva, Kseniya and Werner, Frank},
     title = {A {Finite} {Characterization} and {Recognition} of {Intersection} {Graphs} of {Hypergraphs} with {Rank} at {Most} 3 and {Multiplicity} at {Most} 2 in the {Class} of {Threshold} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {13--28},
     publisher = {mathdoc},
     volume = {37},
     number = {1},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a1/}
}
TY  - JOUR
AU  - Metelsky, Yury
AU  - Schemeleva, Kseniya
AU  - Werner, Frank
TI  - A Finite Characterization and Recognition of Intersection Graphs of Hypergraphs with Rank at Most 3 and Multiplicity at Most 2 in the Class of Threshold Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 13
EP  - 28
VL  - 37
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a1/
LA  - en
ID  - DMGT_2017_37_1_a1
ER  - 
%0 Journal Article
%A Metelsky, Yury
%A Schemeleva, Kseniya
%A Werner, Frank
%T A Finite Characterization and Recognition of Intersection Graphs of Hypergraphs with Rank at Most 3 and Multiplicity at Most 2 in the Class of Threshold Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 13-28
%V 37
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a1/
%G en
%F DMGT_2017_37_1_a1
Metelsky, Yury; Schemeleva, Kseniya; Werner, Frank. A Finite Characterization and Recognition of Intersection Graphs of Hypergraphs with Rank at Most 3 and Multiplicity at Most 2 in the Class of Threshold Graphs. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 1, pp. 13-28. http://geodesic.mathdoc.fr/item/DMGT_2017_37_1_a1/

[1] L.W. Beineke, Derived graphs and digraphs, in: Beitrage zur Graphentheorie, H. Sachs, H.-J. Voss, H.-J. Walter (Ed(s)), (Leipzig, Teubner, 1968) 17–33.

[2] J.C. Bermond and J.C. Meyer, Graphs representatif des arêtes d’un multigraphe, J. Math. Pures Appl. 52 (1973) 299–308.

[3] V. Chvátal and P.L. Hammer, Set-Packing and Threshold Graphs (Comp. Sci. Dept. Univ. of Waterloo, Ontario, 1973).

[4] D.G. Degiorgi and K. Simon, A dynamic algorithm for line graph recognition, Lect. Notes in Comput. Sci. 1017 (1995) 37–48. doi:10.1007/3-540-60618-1_64

[5] S. Földes and P.L. Hammer, Split graphs having Dilworth number two, Canad. J. Math. 29 (1977) 666–672. doi:10.4153/CJM-1977-069-1

[6] M.L. Gardner, Forbidden configurations in intersection graphs of r-graphs, Discrete Math. 31 (1980) 85–88. doi:10.1016/0012-365X(80)90175-2

[7] O.V. Glebova, Yu.M. Metelsky and P.V. Skums, Krausz dimension and its generalizations in special graph classes, Discrete Math. Theor. Comput. Sci. 15 (2013) 107–120.

[8] P. Hliněný and J. Kratochvíl, Computational complexity of the Krausz dimension of graphs, Lect. Notes in Comput. Sci. 1335 (1997) 214–228. doi:10.1007/BFb0024500

[9] M.S. Jacobson, A.E. Kezdy and J. Lehel, Recognizing intersection graphs of linear uniform hypergraphs, Graphs Combin. 4 (1997) 359–367. doi:10.1007/BF03353014

[10] A.G. Levin and R.I. Tyshkevich, Edge Hypergraphs, Diskret. Mat. 5 (1993) 112–129, in Russian.

[11] P.G.H. Lehot, An optimal algorithm to detect a line graph and output its root graph, J. Assoc. Comput. Mach. 21 (1974) 569–575. doi:10.1145/321850.321853

[12] Yu. Metelsky, Split intersection graphs of hypergraphs with bounded rank, Vestsi Nats. Akad. Navuk Belarusi. Ser. Fiz.-Mat. Navuk 3 (1997) 117–122, in Russian.

[13] Yu. Metelsky and K.N. Shchamialiova, Finite characterizability of intersection graphs of hypergraphs with bounded rank and multiplicity in the class of split graphs, Vestn. Beloruss. Gos. Univ. Ser. 1 Fiz. Mat. Inform. 1 (2008) 102–105, in Russian.

[14] Yu. Metelsky and R. Tyshkevich, Line graphs of linear 3 -uniform hypergraphs, J. Graph Theory 25 (1997) 243–251. doi:10.1002/(SICI)1097-0118(199708)25:4h243::AID-JGT1i3.0.CO;2-K

[15] R.N. Naik, S.B. Rao, S.S. Shrikhande and N.M. Singhi, Intersection graphs of k-uniform linear hypergraphs, Ann. Discrete Math. 6 (1980) 275–279. doi:10.1016/S0167-5060(08)70711-8

[16] R.N. Naik, S.B. Rao, S.S. Shrikhande and N.M. Singhi, Intersection graphs of k-uniform linear hypergraphs, European J. Combin. 3 (1982) 159–172. doi:10.1016/S0195-6698(82)80029-2

[17] J. Naor and M.B. Novick, An efficient reconstruction of a graph from its line graph in parallel, J. Algorithms 11 (1990) 132–143. doi:10.1016/0196-6774(90)90034-C

[18] S. Poljak, V. Rödl and D. Turzik, Complexity of representation of graphs by set systems, Discrete Appl. Math. 3 (1981) 301–312. doi:10.1016/0166-218X(81)90007-X

[19] N.D. Roussopoulos, A max { m, n } algorithm for determining the graph H from its line graph G, Inform. Process. Lett. 2 (1973) 108–112. doi:10.1016/0020-0190(73)90029-X

[20] P.V. Skums, Krausz decomposition in special classes of split graphs, Vestn. Beloruss. Gos. Univ. Ser. 1 Fiz. Mat. Inform. 3 (2005) 96–100, in Russian.

[21] P.V. Skums, S.V. Suzdal and R.I. Tyshkevich, Edge intersection graphs of linear 3 -uniform hypergraphs, Discrete Math. 309 (2009) 3500–3517. doi:10.1016/j.disc.2007.12.082

[22] V.A. Tashkinov, Characterization of intersection graphs of p-graphs, in: Proc. 5th all-USSR Conference on Problems of Theoretical Cybernetics (Novosibirsk, 1980) 135–137, in Russian.