Complexity of representation of graphs by set systems

DOI10.1016/0166-218X(81)90007-XzbMath0473.68064OpenAlexW1965922177MaRDI QIDQ1158768

Vojtěch Rödl, Daniel Turzík, Svatopluk Poljak

Publication date: 1981

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(81)90007-x

zbMATH Keywords

random graphsNP-complete

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)

Related Items (8)

Local Clique Covering of Claw-Free Graphs ⋮ Clique coverings and claw-free graphs ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ 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 ⋮ Edge intersection graphs of linear 3-uniform hypergraphs ⋮ Edge intersection graphs of linear 3-uniform hypergraphs ⋮ Unique intersectability of diamond-free graphs ⋮ Applications of edge coverings by cliques

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On set systems determined by intersections
• The NP-completeness of the bandwidth minimization problem
• Some simplified NP-complete graph problems
• Intersection graphs of curves in the plane
• Parallel concepts in graph theory
• Incidence matrices and interval graphs
• Graphe représentatif des arêtes d'un multigraphe
• On colouring random graphs
• Covering edges by cliques with regard to keyword conflicts and intersection graphs
• The Representation of a Graph by Set Intersections
• Sur deux propriétés des classes d'ensembles

This page was built for publication: Complexity of representation of graphs by set systems