The complexity of 2-intersection graphs of 3-hypergraphs recognition for claw-free graphs and triangulated claw-free graphs

• DOI: 10.1016/j.dam.2024.05.009
• Publication Date: 2024-05-18T15:40:30Z
• Authors: N. Di Marco; A. Frosini; C. Picouleau
• Keywords: Claw

Given a 3-uniform hypergraph H, its 2-intersection graph G has as vertex set the hyperedges of H and ee′ is an edge whenever e e′ have exactly two common vertices in H. Di Marco et al. prove (2023) that deciding whether NP-complete. Following this result, we study class claw-free graphs. We show recognition problem remains NP-complete for class, but becomes polynomial if consider triangulated