Discussiones Mathematicae Graph Theory (Feb 2017)

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

  • Metelsky Yury,
  • Schemeleva Kseniya,
  • Werner Frank

DOI
https://doi.org/10.7151/dmgt.1916
Journal volume & issue
Vol. 37, no. 1
pp. 13 – 28

Abstract

Read online

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

Keywords