Search

A family of sets is (p , q) - intersecting if every nonempty subfamily of p or fewer sets has at least q elements in its total intersection. A family of sets has the (p , q) - Helly property if every nonempty (p , q) -intersecting subfamily has total intersection of cardinality at least q. The (2 , 1) -Helly property is the usual Helly property. A hypergraph is (p , q) - Helly if its edge family has the (p , q) -Helly property and hereditary (p , q) -Helly if each of its subhypergraphs has the (p , q) -Helly property. A graph is (p , q) - clique-Helly if the family of its maximal cliques has the (p , q) -Helly property and hereditary (p , q) -clique-Helly if each of its induced subgraphs is (p , q) -clique-Helly. The classes of (p , q) - biclique-Helly and hereditary (p , q) -biclique-Helly graphs are defined analogously. In this work, we prove several characterizations of hereditary (p , q) -Helly hypergraphs, including one by minimal forbidden partial subhypergraphs. On the algorithmic side, we give an improved time bound for the recognition of (p , q) -Helly hypergraphs for each fixed q and show that the recognition of hereditary (p , q) -Helly hypergraphs can be solved in polynomial time if p and q are fixed and co-NP-complete if p is part of the input. In addition, we generalize the characterization of p -clique-Helly graphs in terms of expansions to (p , q) -clique-Helly graphs and give different characterizations of hereditary (p , q) -clique-Helly graphs, including one by forbidden induced subgraphs. We give an improvement on the time bound for the recognition of (p , q) -clique-Helly graphs and prove that the recognition problem of hereditary (p , q) -clique-Helly graphs is polynomial-time solvable for p and q fixed and NP-hard if p or q is part of the input. Finally, we provide different characterizations, give recognition algorithms, and prove hardness results for (p , q) -biclique-Helly graphs and hereditary (p , q) -biclique-Helly graphs which are analogous to those for (p , q) -clique-Helly and hereditary (p , q) -clique-Helly graphs. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

A graph is probe (unit) interval if its vertices can be partitioned into two sets: a set of probe vertices and a set of nonprobe vertices, so that the set of nonprobe vertices is a stable set and it is possible to obtain a (unit) interval graph by adding edges with both endpoints in the set of nonprobe vertices. Probe (unit) interval graphs form a superclass of (unit) interval graphs. Probe interval graphs were introduced by Zhang for an application concerning the physical mapping of DNA in the human genome project. The main results of this article are minimal forbidden induced subgraphs characterizations of probe interval and probe unit interval graphs within two superclasses of cographs: P4-tidy graphs and tree-cographs. Furthermore, we introduce the concept of graphs class with a companion which allows to describe all the minimally non-(probe 풢) graphs with disconnected complement for every graph class 풢 with a companion. [ABSTRACT FROM AUTHOR]

Abstract: Probe (unit) interval graphs form a superclass of (unit) interval graphs. A graph is probe (unit) interval if its vertices can be partitioned into two sets: a set of probe vertices and a set of nonprobe vertices, so that the set of nonprobe vertices is a stable set and it is possible to obtain a (unit) interval graph by adding edges with both endpoints in the set of nonprobe vertices. Probe interval graphs were introduced by Zhang for an application concerning with the physical mapping of DNA in the human genome project. In this work, we present characterizations by minimal forbidden induced subgraphs of probe interval and probe unit interval graphs within two superclasses of cographs: P4-tidy graphs and tree-cographs. [Copyright &y& Elsevier]