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

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2024-10, Vol.355, p.232-246
Main Authors: Di Marco, N., Frosini, A., Picouleau, C.
Format: Article
Language:English
Subjects:
Combinatorics
Computer Science
Discrete Mathematics
Intersection graph
Mathematics
NP-complete
Triangulated graph
Uniform hypergraph
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2024.05.009