- Tytuł:
- 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:
-
Metelsky, Yury
Schemeleva, Kseniya
Werner, Frank - Powiązania:
- https://bibliotekanauki.pl/articles/31342190.pdf
- Data publikacji:
- 2017-02-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
intersection graph
hypergraph rank
hypergraph multiplicity
forbidden induced subgraph
threshold graph - Opis:
- We characterize the class $ 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 $ L_3^2 $ in the class of threshold graphs, where n is the number of vertices of a tested graph.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2017, 37, 1; 13-28
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł