A finite characterization and recognition of intersection graphs of hypergraphs with rank at most 3 and multiplicity at most 2 in the class of thresholds graphs

What is it about?

In this paper, the class of intersection graphs of hypergraphs with rank at most 3 and multiplicity at most 2 is characterized by means of a finite list of forbidden induced subgraphs in the class of threshold graphs. There is also given an algorithm with a complexity linearly depending on the number of vertices for the recognition of graphs from the above class.

Featured Image

Why is it important?

It deals with an interesting subject from graph theory.