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

• Autorzy: Yury Metelsky , Kseniya Schemeleva , Frank Werner
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

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

Kategorie tematyczne

• 05C62: Graph representations (geometric and intersection representations, etc.) {For graph drawing, see also }
• 05C70: Factorization, matching, partitioning, covering and packing
• 05C75: Structural characterization of families of graphs
• 05C85: Graph algorithms
• 05C65: Hypergraphs

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2017
• Tom: 37
• Numer: 1
• Strony: 13-28

Daty

wydano

2017-02-01

otrzymano

2015-02-26

poprawiono

2016-01-29

zaakceptowano

2016-01-29

online

2017-01-13

Twórcy

autor

Yury Metelsky

• Department of Mathematical Cybernetics, Mechanics and Mathematics Faculty, Belarusian State University, Nezavisimosti Ave. 4, 220030 Minsk,

autor

Kseniya Schemeleva

• Université Lumière Lyon 2, Laboratoire d’Economie des Transports, 14 avenue Berthelot, 69363 Lyon Cedex 07,

autor

Frank Werner

• Institute of Mathematical Optimization, Otto-von-Guericke-University of Magdeburg, Universitätsplatz 2, 39106 Magdeburg,

Identyfikatory

DOI

10.7151/dmgt.1916