Paper Info
Title
On the hereditary ( p , q )-Helly property of hypergraphs, cliques, and bicliques
Abstract
We prove several characterizations of hereditary (p, q)-Helly hypergraphs, including one by minimal forbidden partial subhypergraphs, and show that the recognition of hereditary (p, q)-Helly hypergraphs can be solved in polynomial time for fixed p but is co-NP-complete if p is part of the input. We also give several characterizations of hereditary (p, q)-clique-Helly graphs, including one by forbidden induced subgraphs, and prove that the recognition of hereditary (p, q)-clique-Helly graphs can be solved in polynomial time for fixed p and q but is NP-hard if p or q is part of the input. We prove similar results for hereditary (p, q)-biclique-Helly graphs.
Year
DOI
Venue
2015
10.1016/j.endm.2015.07.060
Electronic Notes in Discrete Mathematics
Keywords
Field
DocType
forbidden induced subgraphs,forbidden partial subhypergraphs,maximal bicliques,maximal cliques,(p, q)-Helly property,recognition algorithms
Discrete mathematics,Graph,Combinatorics,Constraint graph,Recognition algorithm,Time complexity,Mathematics
Journal
Volume
ISSN
Citations 
50
1571-0653
0
PageRank 
References 
Authors
0.34
6
3
Name
Order
Citations
PageRank
Mitre Dourado19018.43
Luciano N. Grippo2287.79
Martín Darío Safe3238.99