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

Niccolò Di Marco, Andrea Frosini, Christophe Picouleau

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. D…