Search

A graph is concave‐round if its vertices can be circularly enumerated so that the closed neighborhood of each vertex is an interval in the enumeration. In this study, we give a minimal forbidden induced subgraph characterization for the class of concave‐round graphs, solving a problem posed by Bang‐Jensen, Huang, and Yeo [SIAM J. Discrete Math., 13 (2000), pp. 179–193]. In addition, we show that it is possible to find one such forbidden induced subgraph in linear time in any given graph that is not concave‐round. As part of the analysis, we obtain characterizations by minimal forbidden submatrices for the circular‐ones property for rows and for the circular‐ones property for rows and columns and show that, also for both variants of the property, one of the corresponding forbidden submatrices can be found (if present) in any given matrix in linear time. We make some final remarks regarding connections to some classes of circular‐arc 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 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]

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]

A graph is circle if its vertices are in correspondence with a family of chords in a circle in such a way that every two distinct vertices are adjacent if and only if the corresponding chords have nonempty intersection. Even though there are diverse characterizations of circle graphs, a structural characterization by minimal forbidden induced subgraphs for the entire class of circle graphs is not known, not even restricted to split graphs (which are the graphs whose vertex set can be partitioned into a clique and a stable set). In this work, we give a characterization by minimal forbidden induced subgraphs of circle graphs, restricted to split 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]