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
Yury Metelsky ; Kseniya Schemeleva ; Frank Werner
Discussiones Mathematicae Graph Theory, Tome 37 (2017), p. 13-28 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

We characterize the class [...] L32 L32 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 [...] L32 L32 in the class of threshold graphs, where n is the number of vertices of a tested graph.

Publié le : 2017-01-01
EUDML-ID : urn:eudml:doc:287995 
@article{bwmeta1.element.doi-10_7151_dmgt_1916,
     author = {Yury Metelsky and Kseniya Schemeleva and Frank Werner},
     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},
     volume = {37},
     year = {2017},
     pages = {13-28},
     zbl = {1354.05094},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1916}
}

Yury Metelsky; Kseniya Schemeleva; Frank Werner. 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) pp. 13-28. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1916/