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

Abstract

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