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