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

DOI10.7151/DMGT.1916MaRDI QIDQ505460zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Yury Metelsky, Kseniya Schemeleva, Frank Werner

Publication date 23 January 2017

Published in Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported

Full work available at URL https://doi.org/10.7151/dmgt.1916

zbMATH Keywords

intersection graphthreshold graphforbidden induced subgraphhypergraph multiplicityhypergraph rank

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph representations (geometric and intersection representations, etc.) (05C62) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

Recommendations

• On line graphs of linear 3-uniform hypergraphs
• Threshold hypergraphs
• scientific article; zbMATH DE number 6503350
• Edge intersection graphs of linear 3-uniform hypergraphs
• Intersection multigraphs of uniform hypergraphs

Cites work

• scientific article; zbMATH DE number 1107734 (Why is no real title available?)
• scientific article; zbMATH DE number 3286813 (Why is no real title available?)
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• An efficient reconstruction of a graph from its line graph in parallel
• Complexity of representation of graphs by set systems
• Edge intersection graphs of linear 3-uniform hypergraphs
• Forbidden configurations in intersection graphs of r-graphs
• Graphe représentatif des aretes d'un multigraphe
• Intersection Graphs of k-Uniform Hypergraphs
• Intersection graphs of k-uniform linear hypergraphs
• Krausz dimension and its generalizations in special graph classes
• On line graphs of linear 3-uniform hypergraphs
• Recognizing intersection graphs of linear uniform hypergraphs
• Split Graphs Having Dilworth Number Two
• The Krausz decomposition in special classes of split graphs

Cited in

(4)

• Bounds on the nullity, the \(H\)-rank and the Hermitian energy of a mixed graph
• An \(O(n^3)\) time algorithm for recognizing threshold dimension 2 graphs
• The Complexity of 2-Intersection Graphs of 3-Hypergraphs Recognition for Claw-free Graphs and triangulated Claw-free Graphs
• Structure and complexity of 2-intersection graphs of 3-hypergraphs

This page was built for publication: 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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q505460)