On the hereditary $(p, q)$-Helly property of hypergraphs, cliques, and bicliques

Resumen

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.

Publicación
Electronic Notes in Discrete Mathematics 50 (2015), 361–366