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.009MaRDI QIDQ6437641zbMATH OpenOpenAlexFDO

Authors Niccolò Di Marco, Andrea Frosini, Christophe Picouleau

Publication date 23 May 2023

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

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)

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.

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; zbMATH DE number 6503350
• 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

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)