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

Szczegóły
Opis

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
Źródło:: Discussiones Mathematicae Graph Theory; 2017, 37, 1; 13-28
2083-5892
Język:: angielski
Prawa:: CC BY-NC-ND: Creative Commons Uznanie autorstwa - Użycie niekomercyjne - Bez utworów zależnych 4.0
Dostawca treści:: Biblioteka Nauki
: Artykuł

Przejdź do źródła

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.

Informacja

Powiązane pozycje