# 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 (2017)

- Volume: 37, Issue: 1, page 13-28
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topYury Metelsky, Kseniya Schemeleva, and 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 37.1 (2017): 13-28. <http://eudml.org/doc/287995>.

@article{YuryMetelsky2017,

abstract = {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.},

author = {Yury Metelsky, Kseniya Schemeleva, Frank Werner},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {intersection graph; hypergraph rank; hypergraph multiplicity; forbidden induced subgraph; threshold graph},

language = {eng},

number = {1},

pages = {13-28},

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},

url = {http://eudml.org/doc/287995},

volume = {37},

year = {2017},

}

TY - JOUR

AU - Yury Metelsky

AU - Kseniya Schemeleva

AU - Frank Werner

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

VL - 37

IS - 1

SP - 13

EP - 28

AB - 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.

LA - eng

KW - intersection graph; hypergraph rank; hypergraph multiplicity; forbidden induced subgraph; threshold graph

UR - http://eudml.org/doc/287995

ER -

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.