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

Given a 3 -uniform hypergraph H , its 2-intersection graph G has as 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 in Di Marco et al. (2023) that deciding whether a graph G is the 2-intersection graph of a 3 -uniform hypergraph is NP -complete. Following this result, we study the class of claw-free graphs. We show that the recognition problem remains NP -complete for that class, but becomes polynomial if we consider triangulated claw-free graphs. (c) 2024 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).