The Complexity of 2-Intersection Graphs of 3-Hypergraphs Recognition for Claw-free Graphs and triangulated Claw-free Graphs

DOI10.1016/J.DAM.2024.05.009arXiv2305.13932OpenAlexW4397031188MaRDI QIDQ6437641FDOQ6437641

Authors: Niccolò Di Marco, Andrea Frosini, Christophe Picouleau 

Publication date: 23 May 2023

Abstract: Given a 3-uniform hypergraph H, its 2-intersection graph G has for vertex set the hyperedges of H and ee' is an edge of G whenever e and e' have exactly two common vertices in H. Di Marco et al. prove that deciding wether a graph G is the 2-intersection graph of a 3-uniform hypergraph is NP-complete. The main problems we study concern the class of claw-free graphs. We show that the recognition problem remains NP-complete when G is claw-free graphs but becomes polynomial if in addition G is triangulated.

Full work available at URL: https://doi.org/10.1016/j.dam.2024.05.009

Recommendations

• Structure and complexity of 2-intersection graphs of 3-hypergraphs
• Edge intersection graphs of linear 3-uniform hypergraphs
• Intersection multigraphs of uniform hypergraphs
• scientific article
• 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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Hypergraphs (05C65) Graph operations (line graphs, products, etc.) (05C76)

This page was built for publication: The Complexity of 2-Intersection Graphs of 3-Hypergraphs Recognition for Claw-free Graphs and triangulated Claw-free Graphs

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